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

问题描述

问 题

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

例如：

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

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过程，求通用的线性递归转换为尾递归的套路

解决方案

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

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

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

先把线性递归转换成循环

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)
    }
}

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

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

这篇关于javascript - 线性递归 转 尾递归 的过程是怎么得来的？？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！