今天來搞一個遞歸算法。

有一只青蛙，一次能跳一級，也能跳兩級，問跳n級臺階的時候，有幾種方法？

這是一個很簡單的遞歸，它的相應算法似乎也很容易，f(n) = f(n-1)+f(n-2)也就是說，他在第n級臺階跳的方法等于他在n-1級跳的次數(shù)加上n-2級跳的次數(shù)，于是遞推關系式出來了，這個時候只要寫出初始項也就是1級和2級的情況，代碼也就寫出來了

但是這個算法很有問題，運行數(shù)一多，它的運行時間會緊跟著往上走，比如說，當30級臺階的時候，它的運行時間為9秒！80級的時候，它就根本運行不出來了。。。。

這是運行時間

所以這邊重新引入一種新的算法，記憶化遞歸。

這名字聽得高大上，其實核心就一個，我將每次遞歸運算得出的結(jié)果弄個數(shù)組存起來，這樣下次直接用就好了，這是它對應的代碼：

此時，我的每次上兩級函數(shù)的值直接用自數(shù)組，不需要再重新進行計算，而這個算法對應30級臺階的時間為0毫秒，也就是一瞬間就算出來了，應該說變快了很多很多。

這就是今天介紹的記憶化遞歸算法，今后凡是遇到需要提高遞歸效能的，都可以使用記憶化遞歸算法。每天一個，強身健腦，明天見！