尾調(diào)用
在計算機科學(xué)里冲甘，尾調(diào)用是指一個函數(shù)里的最后一個動作是一個函數(shù)調(diào)用的情形：即這個調(diào)用的返回值直接被當(dāng)前函數(shù)返回的情形荷憋。這種情形下稱該調(diào)用位置為尾位置写半。若這個函數(shù)在尾位置調(diào)用本身（或是一個尾調(diào)用本身的其他函數(shù)等等）吏恭，則稱這種情況為尾遞歸惠豺，是遞歸的一種特殊情形辽故。尾調(diào)用不一定是遞歸調(diào)用徒仓，但是尾遞歸特別有用，也比較容易實現(xiàn)誊垢。
在程序運行時掉弛，計算機會為應(yīng)用程序分配一定的內(nèi)存空間症见；應(yīng)用程序則會自行分配所獲得的內(nèi)存空間，其中一部分被用于記錄程序中正在調(diào)用的各個函數(shù)的運行情況狰晚，這就是函數(shù)的調(diào)用棧筒饰。常規(guī)的函數(shù)調(diào)用總是會在調(diào)用棧最上層添加一個新的堆棧幀（stack frame，也翻譯為“棧幀”或簡稱為“幀”）壁晒，這個過程被稱作“入棿擅牵”或“壓棧”（意即把新的幀壓在棧頂）秒咐。當(dāng)函數(shù)的調(diào)用層數(shù)非常多時谬晕，調(diào)用棧會消耗不少內(nèi)存，甚至?xí)伪瑑?nèi)存空間（棧溢出）[1]携取，造成程序嚴重卡頓或意外崩潰攒钳。尾調(diào)用的調(diào)用棧則特別易于優(yōu)化，從而可減少內(nèi)存空間的使用雷滋，也能提高運行速度不撑。[1]其中，對尾遞歸情形的優(yōu)化效果最為明顯晤斩，尤其是遞歸算法非常復(fù)雜的情形焕檬。[1]
一般來說，尾調(diào)用消除是可選的澳泵，可以用实愚，也可以不用。然而兔辅，在函數(shù)編程語言中腊敲，語言標準通常會要求編譯器或運行平臺實現(xiàn)尾調(diào)用消除。這讓程序員可以用遞歸取代循環(huán)而不喪失性能维苔。
定義
尾調(diào)用 (tail call) 指的是一個函數(shù)的最后一條語句也是一個返回調(diào)用函數(shù)的語句碰辅。在函數(shù)體末尾被返回的可以是對另一個函數(shù)的調(diào)用，也可以是對自身調(diào)用（即自身遞歸調(diào)用）
尾遞歸
若函數(shù)在尾位置調(diào)用自身（或是一個尾調(diào)用本身的其他函數(shù)等等）蕉鸳，則稱這種情況為尾遞歸乎赴。尾遞歸也是遞歸的一種特殊情形。尾遞歸是一種特殊的尾調(diào)用潮尝，即在尾部直接調(diào)用自身的遞歸函數(shù)榕吼。對尾遞歸的優(yōu)化也是關(guān)注尾調(diào)用的主要原因。尾調(diào)用不一定是遞歸調(diào)用勉失，但是尾遞歸特別有用羹蚣，也比較容易實現(xiàn)。
尾遞歸在普通尾調(diào)用的基礎(chǔ)上乱凿，多出了2個特征：
- 在尾部調(diào)用的是函數(shù)自身 (Self-called)顽素；
- 可通過優(yōu)化咽弦，使得計算僅占用常量棧空間 (Stack Space)胁出。
優(yōu)化尾遞歸的分析與示例
對函數(shù)調(diào)用在尾位置的遞歸或互相遞歸的函數(shù)型型，由于函數(shù)自身調(diào)用次數(shù)很多，遞歸層級很深全蝶，尾遞歸優(yōu)化則使原本 O(n) 的調(diào)用椖炙猓空間只需要 O(1)。因此一些編程語言的標準要求語言實現(xiàn)進行尾調(diào)用消除
以Swift為例
func sum(_ n: UInt) -> UInt {
if n == 0 {
return 0
}
return n + sum(n - 1)
}
調(diào)用sum(5)為例抑淫。相應(yīng)的棻谅洌空間變化
sum(5)
5 + sum(4)
5 + (4 + sum(3))
5 + (4 + (3 + sum(2)))
5 + (4 + (3 + (2 + sum(1))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15
可觀察，堆棧從左到右始苇，增加到一個峰值后再計算從右到左縮小砌烁，這往往是我們不希望的，所以在C語言等語言中設(shè)計for, while, goto等特殊結(jié)構(gòu)語句催式，使用迭代函喉、尾遞歸，對普通遞歸進行優(yōu)化荣月，減少可能對內(nèi)存的極端消耗函似。修改以上代碼，可以成為尾遞歸：
func tailSum(_ n: UInt) -> UInt {
func sumInternal(_ n: UInt, current: UInt) -> UInt {
if n == 0 {
return current
} else {
return sumInternal(n - 1, current: current + n)
}
}
return sumInternal(n, current: 0)
}
對比后者尾遞歸對內(nèi)存的消耗
tailSum(5, 0)
tailSum(4, 5)
tailSum(3, 9)
tailSum(2, 12)
tailSum(1, 14)
tailSum(0, 15)
15
則是線性的喉童。
調(diào)用棧
是計算機科學(xué)中存儲有關(guān)正在運行的子程序的消息的棧。有時僅稱“棧”顿天，但棧中不一定僅存儲子程序消息堂氯。幾乎所有計算機程序都依賴于調(diào)用棧，然而高級語言一般將調(diào)用棧的細節(jié)隱藏至后臺牌废。
調(diào)用棧最經(jīng)常被用于存放子程序的返回地址咽白。在調(diào)用任何子程序時，主程序都必須暫存子程序運行完畢后應(yīng)該返回到的地址鸟缕。因此晶框，如果被調(diào)用的子程序還要調(diào)用其他的子程序，其自身的返回地址就必須存入調(diào)用棧懂从，在其自身運行完畢后再行取回授段。在遞歸程序中，每一層次遞歸都必須在調(diào)用棧上增加一條地址番甩，因此如果程序出現(xiàn)無限遞歸（或僅僅是過多的遞歸層次）侵贵，調(diào)用棧就會產(chǎn)生棧溢出。
在Swift中編譯器在Debug 模式下并不會對尾遞歸進行優(yōu)化缘薛。我們可以在 scheme 設(shè)置中將 Run 的配置 改為 Release窍育。
階乘的例子
//普通遞歸
func notailFactorial(_ n:Int) -> Int {
if n == 1 {
return 1
}
return n * notailFactorial(n-1)
}
//尾遞歸
func factorial(_ n: Int) -> Int {
func iter(product:Int , counter: Int = 1) -> Int {
if product <= 1{
return counter
} else {
return iter(product: product-1, counter: counter+product)
}
}
return iter(product: n)
}
