跳臺階引起的for循環(huán)和遞歸地比較思考
lintcode上面的一個(gè)題目：
描述
假設(shè)你正在爬樓梯塞琼，需要n步你才能到達(dá)頂部。但每次你只能爬一步或者兩步愧膀，你能有多少種不同的方法爬到樓頂部拦键？
您在真實(shí)的面試中是否遇到過這個(gè)題？
樣例
比如n=3檩淋，1+1+1=1+2=2+1=3芬为，共有3種不同的方法
返回 3
這題不難，就是個(gè)為斐波納契數(shù)蟀悦，f(n)=f(n-1)+f(n-2)
那我直接拿遞歸來寫：
遞歸寫法
看上去好簡單媚朦，好簡潔，測試沒問題日戈，提交询张。結(jié)果：
錯(cuò)誤提示
輸入39的時(shí)候，時(shí)間超時(shí)浙炼，太沒耐心了份氧。。鼓拧“牖穑看了下人家的代碼，竟然是for寫的：
for循環(huán)
就是把數(shù)據(jù)列舉出來季俩，然后求最后兩位的和。梅掠。酌住。但是速度為啥比遞歸快店归？
后來百度到母函數(shù)遞歸方法的時(shí)間復(fù)雜度（http://www.cnblogs.com/python27/archive/2011/12/09/2282486.html）：
母函數(shù)遞歸方法的時(shí)間復(fù)雜度
呈指數(shù)增長，那就沒有O（n）的速度快了酪我∠矗看來是原來學(xué)遞歸一直沒注意時(shí)間復(fù)雜度，以后注意點(diǎn)都哭。
作者小白秩伞，有錯(cuò)誤的地方，望大神指出欺矫。謝謝纱新！
