javascript - 线性递归 转 尾递归 的过程是怎么得来的？？

Question

参考的资料（阮一峰）：链接描述

例如：

这里有一个线性递归函数（斐波那契数列）：

function f(n) {
  if ( n <= 1 ) {return 1};

  return f(n - 1) + f(n - 2);
}

f(10); // 89

改进=》尾递归：

function f(n , ac1 = 1 , ac2 = 1) {
  if( n <= 1 ) {return ac2};

  return f(n - 1, ac2, ac1 + ac2);
}

f(10) // 89

这是怎么转化得来的？？

我现在的感觉是
A过程：无法直接通过线性递归代码转换成尾递归，直观表现就是，没法在看到线性递归代码第一眼就能够不经思考的按照一定的格式转换成尾递归

我更倾向的是一个这样的过程：
B过程：线性递归==>原理剖析==>代码重构==>尾递归

所以，我感到疑惑的是：如果线性递归转换为尾递归的过程如B过程，上述改造后的尾递归函数怎么得来的（实际就是看不懂那个尾递归函数要体现的功能...汗！）？求释疑。如果如A过程，求通用的线性递归转换为尾递归的套路

Answer 1

题主要思路的话，简单说一下我的思路吧，当然每个人可能不一样

另外，通用的套路的套路应该是不存在的，只能根据这个递归函数的思路，理解了之后才能做转换

以题里的斐波那契数列为例：

先把线性递归转换成循环

let f = (n) => {
    var stack = [1, 1]
    for (let i = 2; i <= n; i++) {
        stack[i] = stack[i - 1] + stack[i - 2]
    }
    return stack[n]
}

这里用stack模拟了递归调用中的调用栈，可以看出来，虽然最后只需要stack[n]
但在求值过程中，吧stack[0]~stack[n]全部求出并存放在了栈里
但实际上并不需要，在求完stack[i]后，stack[i - 2]就没有必要存在了
也就是说只需要暂存当前值和上一个求出的值
所以可以优化一下

let f = (n) => {
    let current = 1, prev = 1
    for (let i = 2; i <= n; i++) {
        let oldCurrent = current
        current = current + prev
        prev = oldCurrent
        /*  要推出和题例里一样的求值方式的话应该这样写，上面用了一个临时变量更容易理解
            current = current + prev
            prev = current - prev
        */
    }
    return current
}

这样就只用到了两个临时变量current和prev，不再需要用到栈了
是不是就和尾递归优化所要达到的效果一样了？
到这里我觉的应该都能推出对应的尾递归函数了

let f = (n, current = 1, prev = 1) => {
    if (n <= 1) {
        return current
    } else {
        current = current + prev
        prev = current - prev
        return f(n - 1, current, prev)
    }  
}

再简化一下

let f = (n, current = 1, prev = 1) => {
    if (n <= 1) {
        return current
    } else {
        return f(n - 1, current + prev, current)
    }
}

题例里的尾递归优化就出来了

(写完才发现和题例里的函数参数顺序搞反了...)

Answer 2

我觉得应该不存在这样一种通用的套路可以把非尾递归的函数转化为尾递归的函数。否则的话还要程序员做尾递归优化干什么呢？编译器自己就应该能识别出所有的递归函数，然后自动进行尾递归优化了。

进行尾递归优化肯定是要观察原本的函数的，然后想办法把 return 的值写成一个简单的函数调用。这只能具体情况具体分析。

Answer 3

你的描述太复杂了，我都快看不懂了。。。

我这么给你讲一下，你就能明白这两个的区别了。

线性递归函数
当执行f(10)的时候，会在其作用域内生成两个变量，返回出来。但这两个变量又需要计算才能得到，所以，这个两个变量的内存不能回收，要一直等待f(10-1)和f(10-2)的返回。

然后就一直递归了，这就多了4个变量在内存里了，然后继续递归。

// ...

直到最后 n<=1 了，开始返回，并依次回收内存。
如果计算过大，可能直接爆栈。

尾递归
从f(10)开始，直接返回一个函数，并给这个函数多传了两个参数 10-1和10-2。

敲黑板，重点来了。
这个时候在函数作用域内除了这个被返回的函数，再没有其他变量，然后在最新的v8引擎中，针对了这种情况做了尾递归优化：就是只剩下一个待执行的函数，再无其他被引用的变量（或者说可被回收的变量），然后回收掉这个母函数，继续执行这个被返回的子函数。

这样子，在内存中就使用是一个函数的作用域块和引用，不会像线性递归一样堆叠作用域，也就不会爆栈了。

说的比较啰嗦，不知道看懂没。

Answer 4

概念方面楼上也解释了，那么我就斐波那契函数的问题发表一下看法吧

像这类数学问题，我觉得是不能简单地靠套路去转换的，譬如f(n - 1) + f(n - 2)和n * f(n - 1)的处理逻辑是不同的，所以节省的机器效率只能靠人去分析优化了

先解释一下阮一峰的做法吧，实际上是分析了序列本身的

//先穷举一下原函数运算过程的数，可以发现c(n + 1) == b(n) + c(n), b(n + 1) == c(n)，对应了原函数回调的逻辑
a  b  c
10 1  1
9  1  2
8  2  3
7  3  5
6  5  8
5  8  13
4  13 21
3  21 34
2  34 55
1  55 89

//然后列举一下数列的各项
n
1(n - 1) + 1(n - 2)
取数化简得
2(n - 2) + 1(n - 3)
3(n - 3) + 2(n - 4)
5(n - 4) + 3(n - 5)
...
34(n - 8) + 21(n - 9) //n = 10, 也就是34 * 2 + 21 == 89
55(n - 9) + 34(n - 10) //若把n - 10 < 1 当成1, 也就是55 + 34 == 89

以上系数能对应上

其实根据原迭代函数，能看出是规律是

f(n) => f(n - 1) + f(n - 2) => f(n - 2) + f(n - 3) + f(n - 3) + f(n - 4)

也就是一个大于1的数二叉拆分到1为止的数量

可得函数

function count(n) {
    var previous = typeof n === 'number' ? [n] : n;
    var next = [];
    previous.forEach(function (val) {
        next.push(val - 1 || 1);
        val > 1 && next.push(val - 2 || 1);
    });
    return next[0] == 1 ? next.length : count(next);
}

当然，性能肯定跟代进系数的没得比。。。

暂时只想到这个，如果有更好的想法不妨提出来学习下

Answer 5

我觉得就和var a=1,b=2;a=b+(b=a);差不多的原理吧.....