使用递归方法的斐波那契给了我堆栈溢出

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

该递归问题的一种解决方案是使用动态编程来中断递归。例如，可以应用memoization并允许您像这样实现它private static Map<Integer, Integer> memo = new HashMap<>();static {&nbsp; &nbsp; memo.put(0, 0);&nbsp; &nbsp; memo.put(1, 1);}public static int rFib(int n) {&nbsp; &nbsp; if (memo.containsKey(n)) {&nbsp; &nbsp; &nbsp; &nbsp; return memo.get(n);&nbsp; &nbsp; }&nbsp; &nbsp; int r = rFib(n - 2) + rFib(n - 1);&nbsp; &nbsp; memo.put(n, r);&nbsp; &nbsp; return r;}

Answer 2

不幸的是，您遇到了这个问题，它既是理解递归的最常用的例子，也是应用递归的最糟糕的应用程序。从斐波那契理解递归真的很简单，因为它是一个非常简单的递归算法，你可以向某人解释并理解......这意味着它非常适合编程递归，对吧？抱歉不行。如果我要告诉你你已经知道的事情，我深表歉意，但我知道斐波那契是入门编程中的第一个例子，所以我假设你来自那里。编程中有一种东西叫做堆栈。它的字面意思是这样的，因为它就像一摞纸。当您调用一个函数时，它会将调用该函数、传递参数以及知道如何从函数返回（以及其他一些管理内容）所需的所有信息放入堆栈。当该函数递归调用自身时，它会将另一张工作表放在堆栈顶部。然后该功能放置另一张纸。在功能完成之前不会删除这些工作表......但是由于一个功能无法在另一个功能完成之前完成，它只会不断增长和增长。堆栈只有这么大。故意。为了避免这个问题。通常，递归不用于解决如此深层次的问题。（尾调用递归的人：忽略这个；如果你不知道什么是尾调用递归：也忽略这个。）解决这个问题的方法是不这样做。人们普遍认为，在几乎所有任意递归函数应用程序中，for循环都会更好（更快）工作。