Java尾递归

系统管理员 2023-01-22 08:53 83阅读 0赞

一、序言

尾调用

维基百科

在计算机学里，尾调用是指一个函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接被当前函数的返回结果。此时，该尾部调用位置被称为尾位置。尾调用中有一种重要而特殊的情形叫做尾递归。经过适当处理，尾递归形式的函数的运行效率可以被极大地优化。尾调用原则上都可以通过简化函数调用栈的结构而获得性能优化（称为“尾调用消除”），但是优化尾调用是否方便可行取决于运行环境对此类优化的支持程度如何。

尾递归

维基百科：

若函数在尾位置调用自身（或是一个尾调用本身的其他函数等等），则称这种情况为尾递归。尾递归也是递归的一种特殊情形。尾递归是一种特殊的尾调用，即在尾部直接调用自身的递归函数。对尾递归的优化也是关注尾调用的主要原因。尾调用不一定是递归调用，但是尾递归特别有用，也比较容易实现。

尾递归在普通尾调用的基础上，多出了2个特征：

  • 在尾部调用的是函数自身 （Self-called）；
  • 可通过优化，使得计算仅占用常量栈空间 (Stack Space)。

下面看尾递归在常见语言的情况。
问题：求n的阶乘？

二、尾递归 in Java

递归

方法

  1. /** * 递归写法 * * @param n n * @return 阶乘 */
  2.     public static BigInteger factorialRecursion(final BigInteger n) { 
  3.         if (n.compareTo(BigInteger.ZERO) < 0) { 
  4.             throw new IllegalArgumentException();
  5.         }
  6.         if (n.compareTo(BigInteger.ONE) == 0) { 
  7.             return BigInteger.ONE;
  8.         } else { 
  9.             return factorialRecursion(n.subtract(BigInteger.ONE)).multiply(n);
  10.         }
  11.     }

测试 n = 10w

  1. @Test
  2.    void factorialTailRecursion() { 
  3.        Examination.start();
  4.        BigInteger result = JRecursion.factorialTailRecursion(BigInteger.ONE, BigInteger.valueOf(10000000L));
  5.        System.out.println("计算结果:" + result);
  6.        Examination.end();
  7.    }

运行

  1. java.lang.StackOverflowError
  2.     at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:35)
  3.     at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:38)
  4.     at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:38)
  5.     at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:38)
  6.     at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:38)

不出意外的栈溢出了，看下下面的尾递归写法。

尾递归

尾递归方法

  1. private int factorialTtailRecursion(final int result, final int n) { 
  2.         if (n == 1) { 
  3.                 return result;
  4.         } else { 
  5.                 return factorialTtailRecursion(result * n,  n - 1);
  6.         }
  7. }

测试

case n = 10w

  1. java.lang.StackOverflowError
  2.     at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:35)
  3.     at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:38)
  4.     at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:38)
  5.     at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:38)
  6.     at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:38)

发现没还是溢出了。因为尾递归只是类似于通知了编译器可以做优化，但是编译器优化不优化又是一回事了。Java编译器是不支持尾递归优化，所以该溢出还是溢出。

为啥java不支持呢，网上冲浪一番得出一些结论：

  1. 改变堆栈跟踪，从而使调试程序变得更加困难。我认为Java的主要目标之一是允许程序员轻松调试他们的代码，而堆栈跟踪对于做到这一点至关重要。
  2. 在高度面向对象的编程环境中。由于可以改用迭代，因此语言委员会必须认为不值得添加尾递归

上面这些是Jdk编程语言层面的，Jvm可以使用goto跳转到方法调用的顶部，并带有新的参数值。并且不需要移动堆栈帧或引起安全冲突（Scala,Kotlin支持）。不过使用场景比较严格，等会看下Kotlin怎么搞的，先看下Java还有啥办法没。

Stream懒加载 + 模拟

翻了一下网上资料，发现可以通过模拟栈+Stream的延迟加载来实现尾递归。

用一个函数式接口模拟栈帧

  1. @FunctionalInterface
  2. public interface TailRecursion<T> { 
  3.     /** * 用于递归栈帧之间的连接,惰性求值 * * @return 下一个递归栈帧 */
  4.     TailRecursion<T> apply();
  6.     /** * 判断当前递归是否结束 * * @return 默认为false, 因为正常的递归过程中都还未结束 */
  7.     default boolean isFinished() { 
  8.         return false;
  9.     }
  11.     /** * 获得递归结果,只有在递归结束才能调用,这里默认给出异常,通过工具类的重写来获得值 * * @return 递归最终结果 */
  12.     default T getResult() { 
  13.         throw new Error("递归还没有结束,调用获得结果异常!");
  14.     }
  16.     /** * 及早求值,执行者一系列的递归,因为栈帧只有一个,所以使用findFirst获得最终的栈帧,接着调用getResult方法获得最终递归值 * * @return 及早求值, 获得最终递归结果 */
  17.     default T invoke() { 
  18.         return Stream.iterate(this, TailRecursion::apply)
  19.                 .filter(TailRecursion::isFinished)
  20.                 .findFirst()
  21.                 .get()
  22.                 .getResult();
  23.     }
  24. }

尾调用优化工具类

  1. public class TailInvoke { 
  2.    /** * 统一结构的方法,获得当前递归的下一个递归 * * @param nextFrame 下一个递归 * @param <T> T * @return 下一个递归 */
  3.    public static <T> TailRecursion<T> call(final TailRecursion<T> nextFrame) { 
  4.        return nextFrame;
  5.    }
  7.    /** * 结束当前递归，重写对应的默认方法的值,完成状态改为true,设置最终返回结果,设置非法递归调用 * * @param value 最终递归值 * @param <T> T * @return 一个isFinished状态true的尾递归, 外部通过调用接口的invoke方法及早求值, 启动递归求值。 */
  8.    public static <T> TailRecursion<T> done(T value) { 
  9.        return new TailRecursion<T>() { 
  10.            @Override
  11.            public TailRecursion<T> apply() { 
  12.                throw new Error("递归已经结束,非法调用apply方法");
  13.            }
  15.            @Override
  16.            public boolean isFinished() { 
  17.                return true;
  18.            }
  20.            @Override
  21.            public T getResult() { 
  22.                return value;
  23.            }
  24.        };
  25.    }
  26. }

用尾调用工具类求阶乘方法

  1. /** * 阶乘计算 -- 使用尾递归接口完成 * * @param factorial 当前递归栈的结果值 * @param number 下一个递归需要计算的值 * @return 尾递归接口, 调用invoke启动及早求值获得结果 */
  2.     public static TailRecursion<BigInteger> factorialTailRecursion1(final BigInteger factorial, final BigInteger number) { 
  3.         if (number.equals(BigInteger.ONE))
  4.             return TailInvoke.done(factorial);
  5.         else
  6.             return TailInvoke.call(() -> factorialTailRecursion1(factorial.multiply(number), number.subtract(BigInteger.ONE)));
  7.     }

测试

  1. @Test
  2.    void factorialTailRecursion1() {
  3.        Examination.start();
  4.        BigInteger result = JRecursion.factorialTailRecursion1(BigInteger.ONE, BigInteger.valueOf(100000L)).invoke();
  5.        System.out.println("计算结果:" + result);
  6.        Examination.end();
  7.    }

没有溢出，测试通过。

  1. 计算结果:28242294079603478742934215780245355184774949260912248505789180865429779509010630178725517714138311636107136117373619629514749961831239180227260734090938324220055569688667840380377379444961268380147875111966906386044926144538111370090160766866405407... //省略n多行
  3. ---------------您的代码执行时间为：3823.95 ms, 消耗内存：668.82 M + !---------------

三、尾递归 in kotlin

4.1 递归

递归阶乘

  1. /** * 递归写法 * * @param n n * @return 阶乘 */
  2.     fun factorialRecursion(n: BigInteger): Int { 
  3.         require(n >= BigInteger.ZERO)
  4.         return if (n.compareTo(BigInteger.ONE) == 0) { 
  5.             1
  6.         } else { 
  7.             factorialRecursion(n.subtract(BigInteger.ONE).multiply(n))
  8.         }
  9.     }

测试 n =10w

溢出。

尾递归写法

代码

  1. /** * 尾递归写法 * * @param result res * @param n n * @return res */
  2.     tailrec fun factorialTailRecursion(result: BigInteger, n: BigInteger): BigInteger? { 
  3.         return if (n == BigInteger.ONE) { 
  4.             result
  5.         } else { 
  6.             factorialTailRecursion(result.multiply(n), n.subtract(BigInteger.ONE))
  7.         }
  8.     }

tailrec关键字表明了这个函数需要编译器帮我优化下，前提是符合尾递归调用形式的。

测试

  1. 计算结果：2824229407960347874293421578024535518477494926091224850578918086542977950901063017872551771413831163610713611737361962951474996183123918022726073409093832422005556968866784038037737944496126838014787511196690638604492614453811137009016076686640540717056595226129804195835677890904754151287114083692425153529309626067227103874424608863545436398293174776177553262185112647485586491818
  2. ---------------您的代码执行时间为：4225.34 ms, 消耗内存：39.42 M + !---------------

为啥Java不行Kotlin行，真是气抖冷。Java还能不能好了，看一下测试方法的字节码。

  1. public final tailrecFib2(III)I
  2.     // annotable parameter count: 3 (visible)
  3.     // annotable parameter count: 3 (invisible)
  4.    L0
  5.     LINENUMBER 41 L0
  6.     ILOAD 3
  7.     IFNE L1
  8.    L2
  9.     LINENUMBER 42 L2
  10.     ILOAD 1
  11.     IRETURN
  12.    L1
  13.     LINENUMBER 44 L1
  14.     ILOAD 2
  15.     ILOAD 1
  16.     ILOAD 2
  17.     IADD
  18.     ILOAD 3
  19.     ICONST_1
  20.     ISUB
  21.     ISTORE 3
  22.     ISTORE 2
  23.     ISTORE 1
  24.     GOTO L0
  25.    L3
  26.    L4
  27.     LOCALVARIABLE this Lcom/robbendev/blog/recursion/KRecursion; L0 L4 0
  28.     LOCALVARIABLE a I L0 L4 1
  29.     LOCALVARIABLE b I L0 L4 2
  30.     LOCALVARIABLE n I L0 L4 3
  31.     MAXSTACK = 4
  32.     MAXLOCALS = 4

关键代码是GOTO LO可以看到编译的时候是转成goto调到L0，跟刚才说的一样。还是在同一个方法内，所以不会有栈溢出了。

四、尾递归 in JavaScript

按es6 js已经支持尾递归了，不过只在严格模式下支持。
正常模式下，函数内部有两个变量，可以跟踪函数的调用栈。

  • arguments：返回调用时函数的参数。
  • func.caller：返回调用当前函数的那个函数。
    感觉和Java类似，要用到栈上的信息就不能随便修改栈。

递归

  1. function factorialRecursion(n) { 
  2.     if (n === 1) { 
  3.         return 1;
  4.     } else { 
  5.         return n * factorialRecursion(n);
  6.     }
  7. }
  8. factorialRecursion(100000); //溢出

尾递归

es6严格模式支持尾递归

  1. "use strict";
  3. function factorialTailRecursion(result, n) { 
  4.     if (n === 1) { 
  5.         return result;
  6.     } else { 
  7.         return factorialTailRecursion(result * n, n - 1);
  8.     }
  9. }
  11. factorialTailRecursion(100000); //正常运行

不过实际意义不大，浏览器支持的少，为了兼容性也不会用严格模式的代码去跑。

蹦床函数

  1. function trampoline(f) {   
  2.   while (f && f instanceof Function) { 
  3.     f = f()
  4.   }
  5.   return f
  6. }
  8. function f(n, a = 0, b = 1) {   
  9.   if (n > 0) { 
  10.     [a, b] = [b, a + b]
  11.     return f.bind(null, n - 1, a, b)
  12.   } else { 
  13.     return a
  14.   }
  15. }
  18. trampoline(100000); //正常运行

五、小结






























递归求10w阶乘 Java Js Kotlin
递归 StackOverFlow StackOverFlow StackOverFlow
尾递归 StackOverFlow 严格模式通过 通过
其他 模拟栈帧+懒加载 蹦床函数通过 /

六、参考资料

https://www.cnblogs.com/invoker-/p/7723420.html
https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8

作者 胡骆宾

发表评论

表情：
评论列表 （有 0 条评论，83人围观）

还没有评论，来说两句吧...

相关阅读

    相关 Java尾递归

    一、序言 尾调用 维基百科 > 在计算机学里，尾调用是指一个函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接被当前函数的返回结果。

    系统管理员系统管理员/ 0 赞/ 84 阅读

    相关 尾递归

    尾递归 如果要说尾递归的话，那么首先应该先说一下递归函数。递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但是循环的逻辑不如递归清晰易理解

    刺骨的言语ヽ痛彻心扉刺骨的言语ヽ痛彻心扉/ 0 赞/ 298 阅读

    相关 python 递归 之 尾递归

    递归函数可以方便的处理一些事物，但普通的递归是栈的堆积，如果堆积的过多就占用过多的内存资源，形象的一些递归就是就像是塔一样，从下至上层层叠加，直到，到达python的限制抛出异

    桃扇骨桃扇骨/ 0 赞/ 408 阅读

    相关 尾递归

    什么是尾递归 什么是尾递归呢?(tail recursion), 顾名思议，就是一种“不一样的”递归，说到它的不一样，就得先说说一般的递归。对于一般的递归，比如下面

    逃离我推掉我的手逃离我推掉我的手/ 0 赞/ 304 阅读

    相关 尾递归

    尾递归就是说一个递归函数，在return语句中调用了这个递归函数本身，如图所示。从理论上来说，尾递归都可以用非递归的方法实现。 ![这里写图片描述][70] [70]

    秒速五厘米秒速五厘米/ 0 赞/ 290 阅读

    相关 尾递归

    1、递归 简单的来说递归就是一个函数直接或间接地调用自身，是为直接或间接递归。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满

    傷城~傷城~/ 0 赞/ 332 阅读