java程序员到底该不该了解一点算法(一个简单的递归计算斐波那契数列的案例说明算法对程序的重要性)

为什么说 “算法是程序的灵魂这句话一点也不为过”，递归计算斐波那契数列的第50项是多少？

方案一：只是单纯的使用递归，递归的那个方法被执行了250多亿次，耗时1分钟还要多。

方案二：用一个map去存储之前计算出的某一项的数据map<n, feibo(n)>，当后面项需要使用前面项的值时，只需要从map中取即可，递归的那个方法仅仅行了97次，耗时还不到1ms。

而这仅仅是计算第50项的值，再往大去计算的话，方案一耗时会更久，因为执行的次数是呈现指数增加的，而且递归的次数过多还有可能会出现栈溢出的问题。

演示如下所示：

package recursion;

import java.util.HashMap;
import java.util.Map;

import org.junit.Test;

/**      
 * @author: 攻城狮小白
 * @creationTime: 2017年11月27日 上午9:47:51
 * @description: 斐波那契数列结合备忘录算法的简单使用
 */
public class MemorandumDemo {
    //计算方法执行次数
    private long count;
    //map集合作为一个备忘录，用来保存已经计算出来的fibo(n)的值
    private Map<Integer, Long> map = new HashMap<>();
    
    //方式一：不使用map集合作为备忘录缓存数据
    public long fibo(Integer n) {
        count++;
        if(n == 1 || n == 2){
            return 1;
        }else{    
            return fibo(n-1) + fibo(n-2);
        }
    }
    //方式二：使用map集合作为备忘录缓存数据
    public long fibo2(Integer n) {
        count++;
        if(n == 1 || n == 2){
            return 1;
        }else{    
            if(!map.containsKey(n)){
                map.put(n, fibo2(n-1) + fibo2(n-2));
            }
            return map.get(n);
        }
    }
    
    @Test
    public void test1(){
        long start = System.currentTimeMillis();
        long result = fibo(50);
        long end = System.currentTimeMillis();;
        System.out.println("计算结果：" + result);
        System.out.println("耗费时间：" + (end-start) + "毫秒");
        System.out.println("方法执行次数："+count);
        /*测试结果
         * 计算结果：12586269025
         * 耗费时间：77318毫秒
         * 方法执行次数：25172538049
        */
    }
    
    @Test
    public void test2(){
        long start = System.currentTimeMillis();
        long result = fibo2(50);
        long end = System.currentTimeMillis();;
        System.out.println("计算结果：" + result);
        System.out.println("耗费时间：" + (end-start) + "毫秒");
        System.out.println("方法执行次数：" + count);
        /*测试结果
         * 计算结果：12586269025
         * 耗费时间：0毫秒
         * 方法执行次数：97
        */
    }
}