递归斐波那契记忆

Question

我在大学为我的Programming
II类编写的程序需要一些帮助。这个问题要求人们使用递归来计算斐波那契数列。必须将计算出的斐波那契数存储在一个数组中，以停止不必要的重复计算并减少计算时间。

我设法使程序在没有数组和存储的情况下运行，现在我试图实现该功能，但遇到了麻烦。我不确定如何组织它。我已经浏览了Google并浏览了一些书，但没有太多帮助我解决如何实施解决方案的方法。

import javax.swing.JOptionPane;
public class question2
{
static int count = 0;
static int [] dictionary;

public static void main(String[] args)
{

int answer;
int num = Integer.parseInt(javax.swing.JOptionPane.showInputDialog("Enter n:"));

javax.swing.JOptionPane.showMessageDialog(null, 
        "About to calculate fibonacci(" + num + ")");

//giving the array "n" elements
dictionary= new int [num];

if (dictionary.length>=0)
dictionary[0]= 0;

if (dictionary.length>=1)
dictionary[0]= 0;
dictionary[1]= 1;


//method call
answer = fibonacci(num);

//output
JOptionPane.showMessageDialog(null,"Fibonacci("+num+") is "+answer+" (took "+count+" calls)");
}



  static int fibonacci(int n)
  {
count++;

// Only defined for n >= 0
if (n < 0) {
  System.out.println("ERROR: fibonacci sequence not defined for negative numbers.");
  System.exit(1);
}

// Base cases: f(0) is 0, f(1) is 1
// Other cases: f(n) = f(n-1) + f(n-2)/
if (n == 0) 
{
  return dictionary[0];
}

else if (n == 1) 
{
  return dictionary[1];
}

else
return dictionary[n] = fibonacci(n-1) + fibonacci(n-2);



}

}

上面是不正确的，我的fib方法的结尾是主要问题。我不知道如何获取它以递归方式将数字添加到数组的正确部分。

Answer 1

您需要在字典中区分已经计算出的数字和未计算出的数字，您现在不知道：您 总是 重新计算数字。

if (n == 0) 
{
  // special case because fib(0) is 0
  return dictionary[0];
}
else 
{
  int f = dictionary[n];
  if (f == 0) {
    // number wasn't calculated yet.
    f = fibonacci(n-1) + fibonacci(n-2);
    dictionary[n] = f;
  }
  return f;
}