使用递归方法的斐波那契使我堆叠溢出

Question

public static int rFib(int n) {
    if(n == 0) {
        return 0;
    }
    if(n == 1) {
        return 1;
    }  
    return n + rFib(n-1);
}

我试图找到将在60秒内计算的最大数量。然后，我将使用迭代方法进行比较。大于10,000的任何数字都会给出堆栈溢流错误。我如何避免这种情况？

Answer 1

此递归问题的一种解决方案是使用动态编程打破递归。例如，可以应用记忆，并允许您像

一样实现它

private static Map<Integer, Integer> memo = new HashMap<>();
static {
    memo.put(0, 0);
    memo.put(1, 1);
}
public static int rFib(int n) {
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    int r = rFib(n - 2) + rFib(n - 1);
    memo.put(n, r);
    return r;
}

Answer 2

不幸的是，您遇到了问题，这既是理解递归的单一示例，也是将递归应用于。

从斐波那契理解递归真的很简单，因为这是一种非常微不足道的递归算法，可以向您解释并理解……这意味着这对编程递归非常有用，对吗？不幸的是，没有。

如果我要告诉您您已经知道的事情，我深表歉意，但是我知道斐波那契是介绍性编程的第一个示例之一，所以我假设那是您来自的地方。

编程中有一个称为堆栈的东西。这实际上是因为它就像一堆论文。当您调用函数时，它将堆栈放在堆栈上调用该功能，传递参数并知道如何从功能（以及其他管理内容）返回的所有信息。当该功能递归地调用自身时，将另一个纸放在堆栈的顶部。然后，该功能将另一个表。在功能完成之前，这些床单不会删除...但是由于一个功能在另一个功能完成之前无法完成，因此它只是成长，增长并增长。

，堆栈只是如此之大。故意。为了避免这个问题。

通常，递归并不用于此类严重问题。（Tail-Call-Chercursive人：忽略这一点；如果您不知道什么是尾巴召集：也忽略了这一点。）

解决此问题的方法是不这样做。人们通常认识到，在几乎所有任意复发功能应用程序中，for循环都可以更好地工作（并且更快）。