前言
本篇介绍的不是什么新知识,而是对前面讲解的一些知识的综合运用。众所周知,递归是解决复杂问题的一个很有效的方式,也是函数式语言的核心,在一些函数式语言中,是没有迭代与while这种概念的,因为此类的循环通通可以用递归来实现,这类语言的编译器都对递归的尾递归形式进行了优化,而Java的编译器并没有这样的优化,本篇就要完成这样一个对于尾递归的优化。
什么是尾递归
本篇将使用递归中最简单的阶乘计算来作为例子
递归实现
/**
* 阶乘计算 -- 递归解决
*
* @param number 当前阶乘需要计算的数值
* @return number!
*/
public static int factorialRecursion(final int number) {
if (number == 1) return number;
else return number * factorialRecursion(number - 1);
}
这种方法计算阶乘比较大的数很容易就栈溢出了,原因是每次调用下一轮递归的时候在栈中都需要保存之前的变量,所以整个栈结构类似是这样的
5
4
3
2
1
------------------->
栈的深度
在没有递归到底之前,那些中间变量会一直保存着,因此每一次递归都需要开辟一个新的栈空间
尾递归实现
任何递归的尾递归版本都十分简单,分析上面栈溢出的原因就是在每次return的时候都会附带一个变量,因此只需要在return的时候不附带这个变量即可。说起来简单,该怎么做呢?其实也很容易,我们使用一个参数来保存上一轮递归的结果,这样就可以了,因此尾递归的阶乘实现应该是这样的代码。
/**
* 阶乘计算 -- 尾递归解决
*
* @param factorial 上一轮递归保存的值
* @param number 当前阶乘需要计算的数值
* @return number!
*/
public static int factorialTailRecursion(final int factorial, final int number) {
if (number == 1) return factorial;
else return factorialTailRecursion(factorial * number, number - 1);
}
使用一个factorial变量保存上一轮阶乘计算出的数值,这样return的时候就无需保存变量,整个的计算过程是(5*4)20 -> (20*3) 60 -> (60*2) 120 -> return 120
这样子通过每轮递归结束后刷新当前的栈空间,复用了栈,就克服了递归的栈溢出问题,像这样的
return
后面不附带任何变量的递归写法,也就是递归发生在函数最尾部,我们称之为'尾递归'。
使用lambda实现编译器的优化
很显然,如果事情这么简单的话,这篇文章也就结束了,和lambda也没啥关系