概述
遞歸函數都不陌生，比如計算n的階乘：
當然，有人可能會這麼寫：
上面兩種方式看著好像沒什麼區別，但是在cpu眼中，可就不一樣了。
分析
函數在調用的時候會開闢一塊函數棧，用來保存函數的局部變量、參數、上一個棧的指針、返回值等信息，當函數調用結束後會銷燬。遞歸函數會一直遞歸下去，上層的函數棧一直不會銷燬，知道遞歸結束，全部退出。
舉個栗子，當調用f(3)的時候，對於上面的第一種情況，函數棧大概長這樣（僅保留參數和返回值，忽略其他內容）：
文字描述就是：
f(1)=1
f(2)=2*f(1)=2*1=2
f(3)=3*f(2)=3*2=6
f(4)=4*f(3)=4*6=24
也就是每一次調用，都會保存本次的變量ｎ以及遞歸調用的返回值，這就會導致如果遞歸的太神，就會開闢太多的內存。
如果使用第二種寫法，會有什麼不同麼？
套用剛才的分析，先用文字描述一下：
f(4, 1)=f(3, 4*1)=f(2, 3*4)=f(1, 2*12)=24
有沒有發現區別，區別就是，前一種寫法要保存一個局部變量n，而後一種寫法，都寫到下一個方法的參數中了。也就是說，第二種方式，可以直接返回下層方法，不需要退回去了。當然，cpu發現這種情況，會複用函數棧，也就是說，函數棧大概是這麼個情況：
看著好像也沒啥區別，但是！因為可以直接返回，上圖的四個棧使用的都是同一個棧。
當遞歸返回的是遞歸調用，並且講調用直接返回，沒有參與運算等，就會被這樣優化，複用棧。
分享到:
閱讀更多 菸草的香味 的文章
