这是我使用java实现的斐波那契数列
/**
* Returns nth fibonacci number
*/
public class fib {
public static void main(String[] args){
System.out.println(fibonacci(12));
}
public static int fibonacci(int n) {
if (n == 0){
return 0;
} else if (n == 1){
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
}
但是使用递归可视化这种方法让我觉得它会快很多。这是 fib(5) 的可视化。http://imgur.com/a/2Rgxs 但这引起了我的思考,请注意,当我们从递归路径的底部冒泡时,我们计算 fib(2)、fib(3) 和 fib(4) 但随后我们在最右上角的分支上重新计算 fib(3)。所以我在想,当我们冒泡备份时,为什么不保存从左分支计算出的 fib(3),这样我们就不会像我目前的方法那样在右分支上进行任何计算,就像回来时的哈希表一样。我的问题是,我如何实现这个想法?