java - 递归斐波那契内存

Question

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

我设法让程序在没有数组和内存的情况下运行，现在我正在尝试实现它，但我被卡住了。我不确定如何构建它。我用 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;
}