級(jí)別： ★☆☆☆☆
標(biāo)簽：「算法」「遞歸」「recursion」
作者： MrLiuQ
審校： QiShare團(tuán)隊(duì)
本篇將介紹遞歸與尾遞歸的相關(guān)內(nèi)容腋寨。
一、什么是“遞歸”欺抗？
遞歸是一種優(yōu)雅的解決問題的方法假哎。
看一段最簡單的遞歸例子：
Fibonacci數(shù)（斐波那契數(shù)）：我們都知道Fibonacci數(shù)的遞推公式為：
- F(0)=F(1)=1占婉，
- 當(dāng)n>=2時(shí)菇绵，F(xiàn)(n)=F(n-1)+F(n-2)
用Python寫澎媒，就是這樣：
def Fibonacci(n):
if(n>=2):
return Fibonacci(n - 1) + Fibonacci(n - 2)
elif (n==0 or n==1):
return 1
else:
return -1
print Fibonacci(20)
遞歸琅绅，簡單來說，就是在運(yùn)行的過程中調(diào)用自己仗考。
遞歸能幫我們處理一些復(fù)雜的算法問題音同，但絕不能濫用遞歸。
在程序設(shè)計(jì)角度痴鳄，循環(huán)的性能要好于遞歸瘟斜。
從開發(fā)角度，使用遞歸痪寻，邏輯上更容易被理解螺句。
所以，要分場合使用遞歸橡类，用好遞歸蛇尚。
二、基線條件和遞歸條件
一個(gè)遞歸的實(shí)現(xiàn)一定少不了基線條件和遞歸條件顾画。
那么取劫，什么是“基線條件”？什么又是“遞歸條件”呢研侣？
| 名稱 | 描述 |
|---|---|
| 遞歸條件 | 函數(shù)調(diào)用自己的條件谱邪。 |
| 基線條件 | 函數(shù)不再調(diào)用自己的條件，從而避免形成無限循環(huán)庶诡。 |
拿上面Fibonacci的例子來說惦银，
def Fibonacci(n):
if(n>=2):
return Fibonacci(n - 1) + Fibonacci(n - 2)
elif (n==0 or n==1):
return 1
else:
return -1
- 遞歸條件：就是
if(n>=2)。 - 基線條件：就是
elif (n==0 or n==1)末誓。
PS：在python中扯俱，
else if的語法是elif。
三喇澡、棧
本節(jié)涉及到了內(nèi)存方面的知識(shí)——調(diào)用棧（call stack）迅栅。
棧是一種簡單的數(shù)據(jù)結(jié)構(gòu)，當(dāng)我們調(diào)用方法時(shí)晴玖，系統(tǒng)會(huì)執(zhí)行“壓椂链妫”操作；當(dāng)我們調(diào)用完方法時(shí)呕屎，系統(tǒng)會(huì)執(zhí)行“出椣芴眩”操作。
簡單來說榨惰，
- 函數(shù)調(diào)用 就意味著 => 申請(qǐng)棧幀拜英，函數(shù)入棧。
- 函數(shù)返回 就意味著 => 推出棧幀琅催，函數(shù)出棧居凶。
PS：不過還有一種特殊的情況：叫做尾調(diào)用優(yōu)化（其本質(zhì)是復(fù)用棧幀，即函數(shù)調(diào)用時(shí)藤抡，不再申請(qǐng)新棧幀侠碧，而是復(fù)用舊的棧幀。）缠黍，在下文
3.3節(jié)會(huì)重點(diǎn)講解弄兜。
3.1 調(diào)用棧
我們來看這樣一段代碼：
def func1(param1):
func2(param1)
func3(param1)
def func2(param2):
print param2
def func3(param3):
print param3
func1(647)
解析：定義了三個(gè)函數(shù)，分別是func1、func2替饿、func3语泽。其中傳入的參數(shù)名為param1、param2视卢、param3踱卵。
而在內(nèi)存中，會(huì)做如下操作：
3.2 遞歸調(diào)用棧
遞歸函數(shù)也會(huì)使用調(diào)用棧据过，我們稱之為“遞歸調(diào)用椡锷埃”。
下面绳锅，請(qǐng)看這個(gè)例子：
def factorial(x):
if x == 1:
return 1
else:
return x * factorial(x-1)
print factorial(3)
解析：這是一個(gè)求階乘的遞歸函數(shù)西饵。傳入?yún)?shù)x，得出xx-1...1的值（x>=1）鳞芙。
而每一次遞歸罗标，都會(huì)申請(qǐng)一個(gè)棧幀，這種棧幀就叫做遞歸調(diào)用棧积蜻。
圖解如下：
3.3 尾遞歸
尾遞歸是一種高級(jí)遞歸方式闯割，它可以不斷的復(fù)用舊棧幀，已達(dá)到最大的內(nèi)存優(yōu)化竿拆。
注意：不是所有語言都支持尾遞歸優(yōu)化（尾調(diào)用優(yōu)化）宙拉。
JavaScript、Objective-C丙笋、Java谢澈、C++等支持尾遞歸優(yōu)化，而Python本身是不支持尾遞歸優(yōu)化的御板。
（關(guān)于iOS中OC的尾調(diào)用優(yōu)化可以看這篇：iOS objc_msgSend尾調(diào)用優(yōu)化機(jī)制詳解）
Q1：什么是尾遞歸锥忿？什么又是尾調(diào)用？
尾遞歸：在函數(shù)最后一步怠肋，僅僅返回調(diào)用了自身敬鬓。（注意僅僅兩字）
尾調(diào)用：在函數(shù)最后一步，僅僅返回了一個(gè)函數(shù)笙各。（注意僅僅兩字）
所以钉答，尾遞歸實(shí)際上是屬于尾調(diào)用的一種特殊情形。
Q2：舉個(gè)尾遞歸的例子杈抢？
int fun(int x) {
if (x > 0)
return fun(x-1);
else
return 1;
}
在函數(shù)的最后一步数尿，僅僅return了本身的函數(shù)。符合尾遞歸惶楼。
Q3：尾遞歸究竟做了什么優(yōu)化右蹦？
兩張對(duì)比圖一目了然：
- 非尾調(diào)用：
- 是尾調(diào)用：
Q4：尾遞歸的本質(zhì)是什么诊杆？
答：棧幀的重復(fù)利用。
推薦文章：
iOS 避免常見崩潰（二）
算法小專欄：選擇排序
iOS Runloop（一）
iOS 常用調(diào)試方法：LLDB命令
iOS 常用調(diào)試方法：斷點(diǎn)
iOS 常用調(diào)試方法：靜態(tài)分析
iOS 消息轉(zhuǎn)發(fā)
