我的递归代码有什么问题？

Question

我有一个循环系列，所以我已经将其转换为递归形式。但是它会显示最大堆栈大小已达到。

相同的代码在n=4时作为fn(4) 可以正常工作，但对于更高的值无法工作。例如n=Math.pow(10, 18)，存在什么问题？

var fn = function(n){   

    // take initial value of f(0) = 1 & f(1) = 1
    if(n===1 || n=== 0)     return 1;

    //calculate on basis of initial values
    else if (n === -1)  return (fn(1) - 3* fn(0) - gn(-1) - 2* gn(0));

    else
        return (3*fn(n-1) + 2 * fn(n-2) + 2* gn(n-1) + 3* gn(n-2));
}; 

var gn = function(n){

        // take initial value of g(0) = 1 & g(1) = 1
        if (n === 1 || n === 0) return 1;

        //calculate on basis of initial values
        else if(n === -1) return ((gn(1) - gn(0)) / 2);

        else return (gn(n-1) + 2* gn(n-2));
    };

- Anurag Jain

Answer 1

问题出在更高的数值上，比如n = Math.pow(10, 18)，栈就不够大了（甚至远远不够）。通常情况下，栈深度只有几千层而已，远远不够。因此，你应该使用迭代代替递归。

- Jashaszun

---

以上代码中是否存在终止问题？ - Anurag Jain

@AnuragJain 如果你没有负数n的话，就不需要担心基本情况了。 - Jashaszun

我实际上正在寻找更快的解决这个问题的方法。在我的情况下，我可以选择记忆化或迭代吗？ - Anurag Jain

@AnuragJain 我建议同时使用两种。 - Jashaszun