基础篇-递归

今天同事在群里分享了一个关于递归解法的经典爬楼梯CASE,问题描述如下：

一个人爬楼梯，每次只能爬1个或2个台阶，假设有n个台阶，那么这个人有多少种不同的爬楼梯方法？

递归算法大家都比较熟悉，大体分三步走：

1.找出将大问题分解为小问题的规律，通过规律写出递推公式。
2.通过递推公式的临界点找出终止条件。
3.将递推公式和终止条件翻译成代码。

(1) 找出将大问题分解为小问题的规律
我们先来思考一下：可以根据第一步的走法把所有走法分为两类：
① 第一类是第一步走了 1 个台阶
② 第二类是第一步走了 2 个台阶
所以 n 个台阶的走法就等于先走 1 阶后，n-1 个台阶的走法 ，然后加上先走 2 阶后，n-2 个台阶的走法。用公式表示就是：

    f(n) = f(n-1) + f(n-2)

(2) 通过递推公式的临界点找出终止条件。
有了递推公式，递归代码基本上就完成了一半。那么接下来考虑递归终止条件。总结如下：
① 假设只有一个台阶，那么只有一种走法，那就是爬 1 个台阶
② 假设有两个台阶，那么有两种走法，一步走完或者分两步来走。
我们找到了终止条件：
f(1) = 1;
f(2) = 2;

(3) 将递推公式和终止条件翻译成代码:

int f(int n) ｛
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
｝

以上内容取自 @周威 分享，内容深入浅出有条理。在此感谢。

写在中间。
这是一篇很吓人的基础篇，超出了我的掌控。
吾之本意真的只想敲个5分钟的代码，写个 Hello World 而已。
可惜世界太大，我还是要看看。

既然这么简单，我就把它Code了一下。

public  int goLadder(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return goLadder(n-1) + goLadder(n-2);
}

我输入了n=10,轻松愉快。

爬个100步如何？年纪轻轻的，应该爬的动吧？行。那咱们就爬一下吧。

  goLadder(100)

结果怎么样呢？程序迟迟没有给出结果，在漫长的等待后你陷入了沉思。年纪大了，爬不动100步了？为了证明一下，你从公司6楼爬到了1楼，又爬了上来，估摸100步了，一看程序居然还没跑完，这是什么鬼？

你若有所思，把程序改了一下：

public static void main(String[] args) {
    for (int i=1;i<100;i++){
        long now = System.currentTimeMillis();
        int count = goLadder(i);
        System.out.println("楼梯数" + i + " count:"+ count + " time:" +  (System.currentTimeMillis()-now));
    }
}

楼梯数1 count:1 time:0
楼梯数2 count:2 time:0
......
楼梯数30 count:1346269 time:3
楼梯数31 count:2178309 time:4
楼梯数32 count:3524578 time:7
楼梯数33 count:5702887 time:13
楼梯数34 count:9227465 time:24
楼梯数35 count:14930352 time:33
楼梯数36 count:24157817 time:68
楼梯数37 count:39088169 time:99
楼梯数38 count:63245986 time:143
楼梯数39 count:102334155 time:223
楼梯数40 count:165580141 time:499
楼梯数41 count:267914296 time:603
楼梯数42 count:433494437 time:876
楼梯数43 count:701408733 time:1341
楼梯数44 count:1134903170 time:2282
楼梯数45 count:1836311903 time:3647
楼梯数46 count:-1323752223 time:5852
楼梯数47 count:512559680 time:9561
楼梯数48 count:-811192543 time:15028
楼梯数49 count:-298632863 time:26480
楼梯数50 count:-1109825406 time:40658
楼梯数51 count:-1408458269 time:67522
楼梯数52 count:1776683621 time:105712

先不论里面的解法数count值已经溢出，你观察了下这个执行时间似乎符合斐波那契数列规律啊。你大致算了一下，到100步估计要100年。

人生苦短！我要向天再借500年！

仔细分析一下程序，以 n=6 为例，解法路径如下：

image.png

可以很清楚的看到，子树f(4)计算了2遍，f(3)更是计算了3遍。这里已经可以意识到越往上，层次越多重复计算更多！
那我们怎么优化这个过程呢？显而易见，我们要把某些中间计算结果传进去。

另外，因为int类型溢出，改为了long类型。

public static long goLadderTail(long n, long ret1, long ret2) {
        if(n == 1) {
            return ret1;
        }
        return goLadderTail(n - 1, ret2, ret1 + ret2);
}

如n=6时，执行次序如下：

n	ret1	ret2
6	1	2
5	2	3
4	3	5
3	5	8
2	8	13
1	13	21

ret1就是第n项的值，ret2就是第n+1项的值。

goLadderTail(floorNum,1,2);

跑100楼轻轻松松就完成了。问题是不是就结束了呢？

咱们跑个100万楼。n=1000000结果如下：

Exception in thread "main" java.lang.StackOverflowError

为什么会栈溢出？

如果你还记得本科教程，改写的时候我们这个函数已经是个尾递归了啊。
让我们看下百科中是怎么描述尾递归的：

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。
当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。
尾递归函数的特点是在回归过程中不用做任何操作，大多数现代的编译器会利用这种特点自动生成优化的代码。

当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。
编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句。
于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。
通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。

根据这个说法，不同于正常的递归，尾递归的栈因为是覆盖的，栈空间不会越来越多，所以是不可能抛出StackOverflowError的，那到底是为什么呢？

答案是Java编译器并没有优化尾递归！

参见：
https://stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations
https://stackoverflow.com/questions/3616483/why-does-the-jvm-still-not-support-tail-call-optimization

好像感觉自己太【南】了。好吧，方法总是有的。

一：放弃递归，使用迭代
递归还是迭代

public static BigInteger goLadderTailWhile(BigInteger n, BigInteger ret1, BigInteger ret2) {
        while (true) {
            if (n.intValue() <= 0)
                return BigInteger.valueOf(0);

            if (n.intValue() == 1) {
                return ret1;
            }
            n = n.subtract(BigInteger.valueOf(1));

            BigInteger tmp = ret1;
            ret1 = ret2;
            ret2 = tmp.add(ret2);
        }
    }

另外，为了解决Long类型溢出，改用了BigInteger类型。

二：使用Lambda惰性求值机制来延迟递归的调用，从而实现栈帧的复用

@FunctionalInterface
public interface TailRecursion<T> {
    TailRecursion<T> apply();
    default boolean isComplete() { return false; }
    default T result() { throw new Error("not implemented"); }
    default T invoke() {
        return Stream.iterate(this, TailRecursion::apply)
            .filter(TailRecursion::isComplete)
            .findFirst()
            .get()
            .result();
    }
}

public class TailInvoke {
    /**
     * 获得当前递归的下一个递归
     * @param nextCall 下一个递归
     * @return 下一个递归
     */
    public static <T> TailRecursion<T> call(final TailRecursion<T> nextCall) {
        return nextCall;
    }

    /**
     * 结束当前递归，设置最终返回结果
     * @param value 最终递归值
     */
    public static <T> TailRecursion<T> done(T value) {
        return new TailRecursion<T>() {
            @Override
            public TailRecursion<T> apply() {
                throw new Error("递归已经结束,非法调用apply方法");
            }
            @Override
            public boolean isComplete() {
                return true;
            }
            @Override
            public T result() {
                return value;
            }
        };
    }
}

public static TailRecursion<BigInteger> goLadderTailLambda(BigInteger n, BigInteger ret1, BigInteger ret2) {
        if (n.intValue()<=0) return TailInvoke.done(BigInteger.valueOf(0));

        if(n.intValue() == 1) {
            return TailInvoke.done(ret1);
        }
        return TailInvoke.call(() -> goLadderTailLambda(n.subtract(BigInteger.valueOf(1)), ret2, ret1.add(ret2)));
    }

这个问题已经上升到违反常识的解法了。

到这里，问题似乎走到了终点。在这里，先抛出两个结论，留下一个尾巴吧。

1 所有的普通递归都能够转化为尾调用形式（非尾递归，尾递归是尾调用的特例）。
2 所有的尾递归都能够转化为迭代。
(这也是Java并没有优化尾递归的原因.
大佬们觉得这是程序容易做的事情，而如果要自动优化反而是个不小的工作量)

为什么普通递归要转为尾调用形式？为了将递归占用的栈空间转移到堆上，避免爆栈的悲剧。
为什么尾递归要转成迭代？因为某些语言的尾递归依然会爆炸。

那怎么进行尾递归转换呢，这个又涉及到一个很复杂的概念：CPS。
参见知乎当年热帖：
王垠巅峰40行

我已经看不懂这个世界，这个Hello World不简单。
结局似乎并没有非常优雅直观的解法。