HTML5技术

开始Java8之旅(六) -- 使用lambda实现Java的尾递归 - 祈求者-

字号+ 作者:H5之家 来源:H5之家 2017-10-26 10:02 我要评论( )

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

前言

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

什么是尾递归

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

递归实现

(final int number) { if (number == 1) return number; else return number * factorialRecursion(number - 1); }

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

5 4 3 2 1 -------------------> 栈的深度

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

尾递归实现

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

(number) { if (number == 1) return factorial; (factorial * number, number - 1); }

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

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

使用lambda实现编译器的优化

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

设计尾递归的接口

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

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

TailRecursion<T> { TailRecursion<T> apply(); (){ return false; } T getResult() { throw new Error("递归还没有结束,调用获得结果异常!"); } T invoke() { return Stream.iterate(this, TailRecursion::apply) .filter(TailRecursion::isFinished) .findFirst() .get() .getResult(); } }

设计对外统一的尾递归包装类

为了达到可以复用的效果,这里设计一个尾递归的包装类,目的是用于对外统一方法,使得需要尾递归的调用同样的方法即可完成尾递归,不需要考虑内部实现细节,因为所有的递归方法无非只有2类类型的元素组成,一个是怎样调用下次递归,另外一个是递归的终止条件,因此包装方法设计为以下两个

  • 调用下次递归
  • 结束本轮递归
    代码如下
  • TailInvoke { <T> TailRecursion<T> call(final TailRecursion<T> nextFrame) { return nextFrame; } <T> TailRecursion<T> done(T value) { return new TailRecursion<T>() { @Override public TailRecursion<T> apply() { throw new Error("递归已经结束,非法调用apply方法"); } () { return true; } @Override public T getResult() { return value; } }; } }

    完成阶乘的尾递归函数

    通过使用上面的尾递归接口与包装类,只需要调用包装了call与done就可以很轻易的写出尾递归函数,代码如下

    TailRecursion<Integer> number) { if (number == 1) return TailInvoke.done(factorial); else return TailInvoke.call(() -> factorialTailRecursion(factorial + number, number - 1)); }

    通过观察发现,和原先预想的尾递归方法几乎一模一样,只是使用包装类的call与done方法来表示递归的调用与结束
    预想的尾递归

    (number) { if (number == 1) return factorial; (factorial * number, number - 1); }

    测试尾递归函数

    这里作一个说明,因为阶乘的计算如果要计算到栈溢出一般情况下Java的数据类型需要使用BigInteger来包装,为了简化代码,这里的测试仅仅是是测试栈会不会溢出的问题,因此我们将操作符的*改成+这样修改的结果仅仅是结果变小了,但是栈的深度却没有改变。测试代码如下
    首先测试 深度为10W的普通递归

    测试代码

    () { System.out.println(factorialRecursion(100_000)); }

    理所当然的栈溢出了

    java.lang.StackOverflowError at test.Factorial.factorialRecursion(Factorial.java:20) at test.Factorial.factorialRecursion(Factorial.java:20) at test.Factorial.factorialRecursion(Factorial.java:20) at test.Factorial.factorialRecursion(Factorial.java:20) at test.Factorial.factorialRecursion(Factorial.java:20) Process finished with exit code -1

    这里我们测试1000W栈帧的尾递归
    尾递归代码

     

    1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

    相关文章
    • [js高手之路] html5 canvas系列教程 - 开始路径beginPath与关闭路径closePath详解 -

      [js高手之路] html5 canvas系列教程 - 开始路径beginPath与关闭路径c

      2017-09-30 13:01

    • 原来实现项目多环境打包部署是如此的简单 - 程序猿到攻城狮之旅

      原来实现项目多环境打包部署是如此的简单 - 程序猿到攻城狮之旅

      2017-09-21 09:08

    • 开始编写寄几的 CSS 基础库 - Daryl

      开始编写寄几的 CSS 基础库 - Daryl

      2017-07-25 12:01

    • 高中毕业,我想去看看-屌丝程序员的逆袭之旅 - 纯洁的微笑

      高中毕业,我想去看看-屌丝程序员的逆袭之旅 - 纯洁的微笑

      2017-07-06 16:00

    网友点评