斐波那契数列递归算法的优化

public class Fibonacci { //优化使用的数组 static long[] cach = new long[51]; public static void main(String[] args) { long a = System.currentTimeMillis(); System.out.println( fd( 50 ) ); long l = System.currentTimeMillis(); System.out.println( l - a ); long l1 = System.currentTimeMillis(); fd1( 50 ); long l2 = System.currentTimeMillis(); System.out.println( l2 - l1 ); } //未优化的 private static int fd1(int n) { if (n == 1 || n == 2) { return 1; } int a = fd1( n - 1 ) + fd1( n - 2 ); return n; } //优化后的 private static long fd(int n) { // 结束条件 if (n == 1 || n == 2) { return 1; } // 检查数组中有没有计算好的结果，如果有，直接返回结果，如果没有进行计算，并存入数组 // 1.1 如果有，直接返回结果 if (cach[n] != 0) { return cach[n]; } // 1.2 如果没有, 进行计算，并存入数组 long x = fd( n - 1 ) + fd( n - 2 ); cach[n] = x; return x; } } //运行结果 12586269025 0//优化后运行时间的毫秒值 35868//未优化运行时间的毫秒值