Java尾递归_java 尾递归

一、序言

尾调用

维基百科

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

尾递归

维基百科：

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

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

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

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

二、尾递归 in Java

递归

方法

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

测试 n = 10w

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

1
2
3
4
5
6
7
8

运行

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

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

尾递归

尾递归方法

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

测试

case n = 10w

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

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

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

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

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

Stream懒加载 + 模拟

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

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

@FunctionalInterface
public interface TailRecursion<T> {
	/**
	 * 用于递归栈帧之间的连接,惰性求值
	 *
	 * @return 下一个递归栈帧
	 */
	TailRecursion<T> apply();

	/**
	 * 判断当前递归是否结束
	 *
	 * @return 默认为false, 因为正常的递归过程中都还未结束
	 */
	default boolean isFinished() {
		return false;
	}

	/**
	 * 获得递归结果,只有在递归结束才能调用,这里默认给出异常,通过工具类的重写来获得值
	 *
	 * @return 递归最终结果
	 */
	default T getResult() {
		throw new Error("递归还没有结束,调用获得结果异常!");
	}

	/**
	 * 及早求值,执行者一系列的递归,因为栈帧只有一个,所以使用findFirst获得最终的栈帧,接着调用getResult方法获得最终递归值
	 *
	 * @return 及早求值, 获得最终递归结果
	 */
	default T invoke() {
		return Stream.iterate(this, TailRecursion::apply)
				.filter(TailRecursion::isFinished)
				.findFirst()
				.get()
				.getResult();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

尾调用优化工具类

public class TailInvoke {
   /**
    * 统一结构的方法,获得当前递归的下一个递归
    *
    * @param nextFrame 下一个递归
    * @param <T>       T
    * @return 下一个递归
    */
   public static <T> TailRecursion<T> call(final TailRecursion<T> nextFrame) {
   	return nextFrame;
   }

   /**
    * 结束当前递归，重写对应的默认方法的值,完成状态改为true,设置最终返回结果,设置非法递归调用
    *
    * @param value 最终递归值
    * @param <T>   T
    * @return 一个isFinished状态true的尾递归, 外部通过调用接口的invoke方法及早求值, 启动递归求值。
    */
   public static <T> TailRecursion<T> done(T value) {
   	return new TailRecursion<T>() {
   		@Override
   		public TailRecursion<T> apply() {
   			throw new Error("递归已经结束,非法调用apply方法");
   		}

   		@Override
   		public boolean isFinished() {
   			return true;
   		}

   		@Override
   		public T getResult() {
   			return value;
   		}
   	};
   }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

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

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

测试

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

没有溢出，测试通过。

计算结果:28242294079603478742934215780245355184774949260912248505789180865429779509010630178725517714138311636107136117373619629514749961831239180227260734090938324220055569688667840380377379444961268380147875111966906386044926144538111370090160766866405407... //省略n多行

---------------您的代码执行时间为：3823.95 ms, 消耗内存：668.82 M + !---------------

1
2
3
4

三、尾递归 in kotlin

4.1 递归

递归阶乘

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

测试 n =10w

溢出。

尾递归写法

代码

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

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

测试

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

1
2
3

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

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

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

四、尾递归 in JavaScript

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

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

递归

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

尾递归

es6严格模式支持尾递归

"use strict";

function factorialTailRecursion(result, n) {
    if (n === 1) {
        return result;
    } else {
        return factorialTailRecursion(result * n, n - 1);
    }
}

factorialTailRecursion(100000); //正常运行
1
2
3
4
5
6
7
8
9
10
11

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

蹦床函数

function trampoline(f) {  
  while (f && f instanceof Function) {
    f = f()
  }
  return f
}

function f(n, a = 0, b = 1) {  
  if (n > 0) {
    [a, b] = [b, a + b]
    return f.bind(null, n - 1, a, b)
  } else {
    return a
  }
}


trampoline(100000); //正常运行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

五、小结

六、参考资料

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

作者 胡骆宾