Java8使用lambda实现Java的尾递归

Java8引入了lambda表达式，使得Java语言可以使用函数式编程的风格实现一些高级编程技巧，其中利用lambda实现Java的尾递归也是其中之一。

什么是尾递归？

首先，我们需要了解什么是尾递归。尾递归是指一个递归函数最后以递归形式调用自身，而不对返回值进行任何操作直接返回。这样的递归函数成为尾递归。如果一个递归函数不是尾递归，就会在调用自身之前保存中间结果，需要开辟新的栈空间，在程序调用栈过深时容易造成栈溢出。而尾递归则可以通过一些技巧优化为循环，避免栈溢出。

下面我们使用传统的递归方式来实现求斐波那契数列第n项的方法：

public static int fibRecursion(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fibRecursion(n - 1) + fibRecursion(n - 2);
}

因为每次递归都会保存中间结果，需要不断开辟新的栈空间，如果n较大就容易造成栈溢出。

而使用尾递归的方式来实现求斐波那契数列第n项的方法为：

public static int fibTailRecursion(int n, int acc1, int acc2) {
    if (n == 0) {
        return acc1;
    }
    return fibTailRecursion(n - 1, acc2, acc1 + acc2);
}

public static int fib(int n) {
    return fibTailRecursion(n, 0, 1);
}

可以看到，尾递归只保存最后一步的中间结果，并且使用acc1和acc2两个参数来记录前两个斐波那契数，通过不断更新acc1和acc2两个参数达到求解斐波那契数的目的。因为只保存了最后一步的中间结果，并且不断更新acc1和acc2两个参数，避免了栈溢出的问题。

使用lambda实现Java的尾递归

使用Java8提供的lambda表达式，我们可以实现尾递归的优化。需要定义一个函数接口来实现lambda表达式的递归调用：

@FunctionalInterface
public interface TailRecursion<T> {
    TailRecursion<T> apply();

    default boolean isFinished() {
        return false;
    }

    default T getResult() {
        throw new RuntimeException("no result yet");
    }
}

这里的TailRecursion接口使用了Java8的新特性：函数式编程。可以看到它定义了apply()方法表示每一步的递归调用，以及isFinished()和getResult()方法分别表示递归的终止条件和结果返回。这里需要注意，isFinished()默认返回false，也就是说只要apply()方法不断被调用就会继续递归下去。

利用java8的lambda表达式，可以通过如下代码实现斐波那契数列递归：

public static TailRecursion<Integer> fibTailRecursion(int n, int acc1, int acc2) {
    if (n == 0) {
        return new TailRecursion<Integer>() {
            @Override
            public Integer getResult() {
                return acc1;
            }

            @Override
            public TailRecursion<Integer> apply() {
                return finished();
            }

            @Override
            public boolean isFinished() {
                return true;
            }
        };
    }
    return () -> fibTailRecursion(n - 1, acc2, acc1 + acc2);
}

public static TailRecursion<Integer> finished() {
    return new TailRecursion<Integer>() {
        @Override
        public TailRecursion<Integer> apply() {
            throw new RuntimeException("not supported");
        }

        @Override
        public boolean isFinished() {
            return true;
        }

        @Override
        public Integer getResult() {
            throw new RuntimeException("no result yet");
        }
    };
}

public static int fib(int n) {
    return tailRecursion(fibTailRecursion(n, 0, 1)).getResult();
}

public static <T> T tailRecursion(final TailRecursion<T> initial) {
    TailRecursion<T> tr = initial;
    while (!tr.isFinished()) {
        tr = tr.apply();
    }
    return tr.getResult();
}

这里的fibTailRecursion方法中，如果n为0我们就返回一个包含结果的TailRecursion对象；否则返回一个lambda表达式，相当于递归调用函数。isFinished()方法表示递归的终止条件，如果为true表示递归结束，getResult()方法则表示递归结束后的结果返回。tailRecursion方法则用来执行尾递归，使用while循环执行递归调用直到满足结束条件。

尾递归示例

除了斐波那契数列之外，我们可以使用尾递归来求解阶乘。传统递归求解阶乘的代码如下：

public static int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

而使用尾递归的代码如下：

public static TailRecursion<Integer> factorialTailRecursion(final int factorial, final int number) {
    if (number == 1) {
        return new TailRecursion<Integer>() {
            @Override
            public Integer getResult() {
                return factorial;
            }

            @Override
            public TailRecursion<Integer> apply() {
                return finished();
            }

            @Override
            public boolean isFinished() {
                return true;
            }
        };
    }
    return () -> factorialTailRecursion(factorial * number, number - 1);
}

public static int factorial(int n) {
    return tailRecursion(factorialTailRecursion(1, n)).getResult();
}

可以看到，使用尾递归的形式可以避免采用传统递归方法中的栈溢出问题。

总结

以上就是使用lambda实现Java的尾递归的详细攻略。尾递归可以将递归调用转化为循环调用，避免栈空间不足导致的栈溢出错误。Java8引入的lambda表达式可以轻松实现尾递归优化，大家可以根据上面的示例代码自行尝试编写其他递归函数的尾递归优化方法。