JavaScript递归

关于递归

简单理解递归，就是一个函数在内部又调用了自己。

这里有一个视频能让一个人产生直观的印象。

在编程领域，递归思想是解决问题的重要思路。

JavaScript中递归的问题

使用JavaScript语言，使用递归并不能随心所欲。

我们知道每一次函数调用，都要为之在调用栈创建一个区域存放相关内容，如果函数执行完毕返回，则对应的调用栈区域会被从调用栈弹出。

这里调用栈也存在空间的限制，不能无限制增大，当调用栈满的时候，程序运行就会报错了。

因为递归程序存在自己调用自己的情况，而且需要等到满足递归终止条件才会返回，所以从递归开始到结束为止，这系列函数调用都会对应占用调用栈的一块空间。这样，如果递归的次数足够多，调用栈就会满了，程序无法如期执行下去了。

下面是解决这类问题的几种方法。

优化递归改为尾调用

首先说，这个解决方式不推荐，因为JavaScript语言宿主环境普遍不支持。

但是可以说说这种方式的思路：

首先把递归函数改成尾调用函数（就是函数中最后一句是调用自己）
这时，递归中产生的调用栈就没有存在的必要了
需要宿主环境把上述没有必要存在的调用栈清理掉，这样就不会产生爆栈的情况了

修改递归为循环

递归和循环是不同的实现思路，所以，改动起来还是很大的，改后的代码很常规，不那么酷了。

使用Trampoline

Trampoline称为“蹦床”，本质上也类似实物蹦床。使用这种方式，其实也是在执行循环，在蹦床上每弹跳一次，都执行了一步操作。

每一步操作都没有返回一个具体值，而是返回了一个方法，每一步的操作结果都作用在了这个方法的参数上。

这里需要说明的是，使用这种方式改造递归程序，一定要跳出原来递归的思路，后面给出的实例代码中有详细的介绍。

实例

计算斐波那契额数列

使用递归

function Fibonacci(n) {
    if(n==0){
        return 0
    }
    if (n == 1) {
        return 1
    }

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

console.log(Fibonacci(100)) // 会爆栈

使用循环

/**
 * 使用循环得到斐波那契额数列数组
 * @param {Number} num 
 */
function Fibonacci(num){
    if(num<1){
        return [0]
    }
    else if(num==1){
        return [1]
    }else{
        // 初始化 前两项的值，准备循环
        let i = 2, // 循环起点
            f = 0,//  F(n-2)
            s = 1 //  F(n-1)
        let fn = 0 // F(n)
        let arr=[0,1]
        while (i <= num) {
            fn = f + s //F(n)=F(n-2)+F(n-1)
            i++ // 准备计算下一项
            f = s // 更新F(n-2)
            s = fn //更新F(n-1)
            arr.push(fn)
        }
        return arr
    }
}

console.log(Fibonacci(100))

使用Trampoline

其一：

/**
 * 改造的Fibonacci函数，不直接调用自身，形成递归；而是返回一个参数就绪的函数，以备外部调用。
 * 从第2位开始计算数列值，计算结果存入数组，最后返回数组。
 * @param {Number} n 剩余计算次数计数器
 * @param {Number} f 当前计算项的前2项，初始值是数列的第0位：0
 * @param {Number} s 当前计算项的前1项，初始值是数列的第1位：1
 * @param {Array} arr 存放数列的数组
 */
function Fibonacci(n,f=0,s=1,arr=[]){
   
    // 终止条件：到0。返回结果数组
    if(n==0){
        return arr
    }
    // 把f放入数组
    arr.push(f)

    // 返回自身，修改参数以备下次计算：
    // 剩余计算次数减少一次，数组计算项目向后移动一位
    return Fibonacci.bind(null, n - 1, s, (f + s), arr)
}
function Trampoline(fn){
    while (fn && typeof fn === 'function') {
        fn = fn()
    }
    return fn
}
 function work(n,f,s){
     return Trampoline(function(){
        return  Fibonacci(n,f,s)
     })
 }
 console.log(work(100))

其二：

function trampoline(fn) {
    return (...args) => {
        let result = fn(...args);
        while (typeof result === 'function') {
            result = result();
        }
        return result;
    };
}

function fibonacci(count, a = 1, b = 1) {
    const acc = [];

    function inner(count, a, b) {
        if (!count) {
            return acc;
        }
        acc.push(a);

        console.log(count - 1, b, a + b)
        return () => inner(count - 1, b, a + b);
    }

    return trampoline(inner)(count, a, b);
}

console.log(fibonacci(100));

计算阶乘

使用递归

// 阶乘需要使用big Integer,否则无法演示爆栈的情况
function factorial(n) {
    if (n == 1n) return 1n;
    return n * factorial(n - 1n);
}
console.log(
    factorial(100000n) // 会爆栈
)

使用循环

/**
 * 得到从1到n位的阶乘数组
 * @param {BigInt} n  阶乘数组第n位
 */
function factorial(n){
    let rst=1n// 累乘的结果
    let arr=[1]// 存储数列项的数组，第0位为1
    // i:循环计数器；rst：累计计数器；
    for (let i = 1n; i <= n; i++) {
        rst=rst*i
        arr.push(rst)
    }
    return arr
}
console.log(factorial(100000n))

使用Trampoline

function factorial(n, total) {
    if (n == 1) return total;
    // 返回一个 thunk，避免函数调用 
    return factorial.bind(null, n - 1n, n * total);
}

// tramponline 函数 
function trampoline(fn) {
    while (fn && typeof fn === 'function') {
        fn = fn()
    }
    return fn
}

function fac(n, total) {
    return trampoline(function () {
        return factorial(n, total)
    })
}
console.log(
    fac(100000n, 1n)
)

参考

救星：Trampoline（蹦床）

JS得到斐波那契数列