什么是遞歸？

---

用通俗的話來說就像問路，張三問李四，李四問王五，王五問趙六? ?趙六知道答案回復了王五，王五回復了李四，李四回復了張三，問路結束

官方的定義是一個函數(shù)調用其本身

遞歸的特性

---

1.必須有一個明確的停止條件

2.每次更深入一層遞歸時，問題規(guī)模要比上次遞歸都應有所減小

3.遞歸次數(shù)不能太多，否則會造成棧溢出

遞歸的代碼示例

---

?

遞歸函數(shù)在某些時候具有代碼邏輯十分清晰的效果，比如在算數(shù)的階乘的時候。階乘的定義為n! = 1 × 2 × 3 × … × n，示例代碼如下所示：

def jiecheng(n):if n==1:return nelse:return n*jiecheng(n-1)res = jiecheng(5) print(res) #打印結果為120

?遞歸的優(yōu)化方法之尾遞歸優(yōu)化

---

?

因為暫時寫不出例子，用以下代碼來講解尾遞歸優(yōu)化是怎么一回事兒

#不屬于尾遞歸調用 def test1(n):if n==1:return nelse:return n*test1(n-1) #屬于尾遞歸調用 def test2(n):if n==1:return nelse:return test2(n-1)

以上兩行代碼的區(qū)別就在于最后一步，不屬于尾遞歸調用的那個最后一行代碼實際上執(zhí)行步驟如下

res = test1(n-1)? #1

res = n* res? ?#2

在執(zhí)行第一步的時候跳入第二層函數(shù)的時候需要保存第一層函數(shù)的位置，變量等信息在棧中

?

而屬于尾遞歸調用的最后一行代碼執(zhí)行步驟如下

res = test1(n-1)? #1

在跳入第二層函數(shù)的時候第一層的函數(shù)實際上已經(jīng)結束，不需要保存第一層函數(shù)相關的所有信息了。

?

所以尾遞歸調用可以減輕棧的負荷

?

轉載于:https://www.cnblogs.com/codescrew/p/8661044.html

總結

以上是生活随笔為你收集整理的函数递归以及尾递归调用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。