Java8使用lambda实现Java的尾递归
156 浏览量
2020-08-29
00:51:22
上传
评论
收藏 82KB PDF 举报
Java8使用使用lambda实现实现Java的尾递归的尾递归
主要介绍了Java8使用lambda实现Java的尾递归的相关资料,需要的朋友可以参考下
前言前言
本篇介绍的不是什么新知识，而是对前面讲解的一些知识的综合运用。众所周知，递归是解决复杂问题的一个很有效的方式，
也是函数式语言的核心，在一些函数式语言中，是没有迭代与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也没啥关系 :) 然而当你调用上文的尾递归写法之后，发现
并没有什么作用，该栈溢出的还是会栈溢出，其实原因我在开头就已经说了，尾递归这样的写法本身并不会有什么用，依赖的
是编译器对尾递归写法的优化，在很多语言中编译器都对尾递归有优化，然而这些语言中并不包括java，因此在这里我们使用
lambda的懒加载(惰性求值)机制来延迟递归的调用，从而实现栈帧的复用。
资源评论
