Java8使用λ实现Java的尾递归

　　

　　

本篇介绍的不是什么新知识,而是对前面讲解的一些知识的综合运用。众所周知,递归是解决复杂问题的一个很有效的方式,也是函数式语言的核心,在一些函数式语言中,是没有迭代与在这种概念的,因为此类的循环通通可以用递归来实现,这类语言的编译器都对递归的尾递归形式进行了优化,而Java的编译器并没有这样的优化,本篇就要完成这样一个对于尾递归的优化。

　　

　　

本篇将使用递归中最简单的阶乘计算来作为例子

　　

递归实现

　　 　　/* * 　　*阶乘计算——递归解决 　　* 　　* @param数量当前阶乘需要计算的数的值 　　* @return号码! 　　*/公共静态int factorialRecursion(最后一个int数){ 　　如果数量(数量==1)返回; 　　否则返回数量* factorialRecursion (- 1); 　　} 　　 　　

这种方法计算阶乘比较大的数很容易就栈溢出了,原因是每次调用下一轮递归的时候在栈中都需要保存之前的变量,所以整个栈结构类似是这样的

　　

5
　　,4
　　,,3
　　,,,,2
　　,,,,,,1
　　- - - - - - - - - - - - - - - - - -→

　　

,,,,,栈的深度

　　

在没有递归到底之前,那些中间变量会一直保存着,因此每一次递归都需要开辟一个新的栈空间

　　

　　

任何递归的尾递归版本都十分简单,分析上面栈溢出的原因就是在每次返回的时候都会附带一个变量,因此只需要在返回的时候不附带这个变量即可。说起来简单,该怎么做呢& # 63;其实也很容易,我们使用一个参数来保存上一轮递归的结果,这样就可以了,因此尾递归的阶乘实现应该是这样的代码。

　　 　　/* * 　　*阶乘计算,尾递归解决 　　* 　　* @param !上一轮递归保存的值 　　* @param数量当前阶乘需要计算的数的值 　　* @return号码! 　　*/公共静态int factorialTailRecursion(最后一个整数的阶乘,最后一个int数){ 　　如果(数量==1)返回!; 　　否则返回factorialTailRecursion(阶乘*数,数- 1); 　　} 　　 　　

使用一个阶乘变量保存上一轮阶乘计算出的数的值,这样回来的时候就无需保存变量,整个的计算过程是
　　20 (5 * 4)→60 (20 * 3)→(60 * 120 (2)→返回120

　　

这样子通过每轮递归结束后刷新当前的栈空间,复用了栈,就克服了递归的栈溢出问题,像这样的返回后面不附带任何变量的递归写法,也就是递归发生在函数最尾部,我们称之为“尾递归的。

　　

　　

很显然,如果事情这么简单的话,这篇文章也就结束了,和λ也没啥关系:)然而当你调用上文的尾递归写法之后,发现并没有什么作用,该栈溢出的还是会栈溢出,其实原因我在开头就已经说了,尾递归这样的写法本身并不会有什么用,依赖的是编译器对尾递归写法的优化,在很多语言中编译器都对尾递归有优化,然而这些语言中并不包括java,因此在这里我们使用λ的懒加载(惰性求值)机制来延迟递归的调用,从而实现栈帧的复用。

　　

　　

因此我们需要设计一个这样的函数接口来代替递归中的栈帧,通过应用这个函数方法(取名叫应用是因为该方法的参数是一个栈帧,返回值也是一个栈帧,类比函数接口的应用)完成每个栈帧之间的连接,除此之外,我们栈帧还需要定义几个方法来丰富这个尾递归的接口。

　　

应用(连接栈帧,惰性求值)
　　判断递归是否结束
　　得到递归最后的结果
　　执行递归(及早求值)

　　

根据上面的几条定义,设计出如下的尾递归接口

　　 　　/* * 　　*尾递归函数接口 　　* @author:黑客帝国 　　*/@FunctionalInterface 　　公共接口TailRecursion{/* * 　　*用于递归栈帧之间的连接,惰性求值 　　* @return下一个递归栈帧 　　*/TailRecursion应用();/* * 　　*判断当前递归是否结束 　　* @return默认为假,因为正常的递归过程中都还未结束 　　*/默认的布尔结束(){ 　　返回错误; 　　}/* * 　　*获得递归结果,只有在递归结束才能调用,这里默认给出异常,通过工具类的重写来获得值 　　* @return递归最终结果 　　*/默认T getResult () { 　　把新的错误(“递归还没有结束,调用获得结果异常!”); 　　}/* * 　　*及早求值,执行者一系列的递归,因为栈帧只有一个,所以使用findFirst获得最终的栈帧,接着调用getResult方法获得最终递归值 　　* @return及早求值,获得最终递归结果 　　*/默认T invoke () { 　　返回流。迭代(这,TailRecursion::适用) 　　.filter (TailRecursion:结束) 　　.findFirst () 　　. get () 　　.getResult (); 　　} 　　}

Java8使用λ实现Java的尾递归