Java高效斐波那契递归算法
时间: 2024-09-19 15:00:37 浏览: 5
Java中的高效斐波那契递归算法通常会利用记忆化(Memoization)技术来避免重复计算,因为标准的递归版本会因大量重复计算导致效率低下。下面是一个使用缓存(HashMap)存储中间结果的优化版递归实现:
```java
import java.util.HashMap;
public class Fibonacci {
private static HashMap<Integer, Long> memo = new HashMap<>();
public static long fib(int n) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);
memo.put(n, fib(n - 1) + fib(n - 2));
return memo.get(n);
}
// 主函数测试
public static void main(String[] args) {
int n = 40; // 你可以更改这个数字来测试不同规模的斐波那契数列
System.out.println("Fibonacci of " + n + ": " + fib(n));
}
}
```
在这个优化版本中,当我们第一次计算`fib(n)`时,如果`n`已经存在于`memo`中,就直接返回缓存的结果;否则,计算值并将其放入`memo`中供后续调用使用。