編程很復(fù)雜时甚，編程也很簡(jiǎn)單。簡(jiǎn)單的邏輯哈踱，通過代碼組織荒适，就可以變成復(fù)雜程序或者系統(tǒng)。以前學(xué)物理的時(shí)候开镣，老師就說考試的物理題其過程是相當(dāng)復(fù)雜的（簡(jiǎn)單的就沒有必要考了）刀诬。解題方法眾多，分解法即是一個(gè)行之有效的方式邪财。復(fù)雜的過程經(jīng)過分解舅列，會(huì)變成簡(jiǎn)單的定理。如同螺絲卧蜓，輪胎帐要，玻璃都很簡(jiǎn)單，卻能組合而成復(fù)雜的汽車弥奸。
編程也類似榨惠，核心哲學(xué)甚至簡(jiǎn)單得令人發(fā)指，其一是指針盛霎，其二是遞歸赠橙。深入理解者兩個(gè)概念，很多復(fù)雜的系統(tǒng)或者設(shè)計(jì)愤炸，都會(huì)化繁為簡(jiǎn)期揪，一目了然规个。
遞歸
遞歸凤薛，一個(gè)函數(shù)在內(nèi)部調(diào)用自己姓建，就是遞歸。遞歸在生活中也很常見缤苫，例如我們的眼睛速兔，你看對(duì)方的眼睛，對(duì)方的眼睛里面有你活玲，而那里面那個(gè)你又有她涣狗，無限循環(huán)。再比如舒憾，當(dāng)你拿著一面鏡子镀钓，對(duì)著另外一面鏡子的時(shí)候，就會(huì)發(fā)現(xiàn)鏡子之中有你手指的鏡子镀迂，等等掸宛。
尾遞歸
函數(shù)中可以調(diào)用自己成為遞歸，也可以在末尾調(diào)用別的函數(shù)招拙。如果一個(gè)函數(shù)里的最后一個(gè)動(dòng)作是一個(gè)函數(shù)調(diào)用的情形：即這個(gè)調(diào)用的返回值直接被當(dāng)前函數(shù)返回的情形唧瘾。這樣的調(diào)用為尾調(diào)用。如果是尾調(diào)用自己别凤，即為尾遞歸饰序。
尾遞歸是一種形式, 這種形式表達(dá)出的概念可以被某些編譯器優(yōu)化. 尾遞歸的特殊形式?jīng)Q定了這種遞歸代碼在執(zhí)行過程中是可以不需要回溯的(通常的遞歸都是需要回溯的). 如果編譯器針對(duì)尾遞歸形式的遞歸代碼作了這種優(yōu)化, 就可能把原本需要線性復(fù)雜度棧內(nèi)存空間的執(zhí)行過程用常數(shù)復(fù)雜度的空間完成.
尾遞歸通常用于實(shí)現(xiàn)以下重復(fù)的計(jì)算。而一般的語言卻不支持尾遞歸规哪，也就是并沒有被優(yōu)化求豫。例如java, python。它們使用循環(huán)迭代來達(dá)到同樣的效果诉稍。
階乘計(jì)算
解釋遞歸最常用的例子就是階乘算法蝠嘉，下面使用 Python，Elixir杯巨，Scheme分別實(shí)現(xiàn)常用的遞歸算法蚤告。
class Factorial(object):
@classmethod
def recursion(cls, n):
if n == 1:
return 1
return n * cls.recursion(n - 1)
Factorial.recursion(5) # 輸出 120
魔法書（SICP）中簡(jiǎn)單的演示了這個(gè)調(diào)用過程：
recursion(5)
5 * recursion(4)
5 * (4 * recursion(3))
5 * (4 * (3 * recursion(2)))
5 * (4 * (3 * (2 * recursion(1))))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120
函數(shù)調(diào)用之后，會(huì)繼續(xù)調(diào)用自身服爷，并在棧里堆積內(nèi)存杜恰。scheme的解法也很簡(jiǎn)單：
#lang scheme
(define (recursion n)
(if (= n 1)
1
(* n (recursion (- n 1)))))
(recursion 5) ; 輸出 120
同樣，elixir也很容易實(shí)現(xiàn)：
defmodule Factorial do
def recursion(n) when n == 1 do
1
end
def recursion(n) do
n * recursion(n-1)
end
end
IO.puts Factorial.recursion(5) # 輸出 120
上述是遞歸調(diào)用仍源，并不是尾遞歸心褐，如果使用尾遞歸，python代碼如下：
class Factorial(object):
@classmethod
def tail_recursion(cls, n, acc=1):
if n == 1:
return acc
return cls.tail_recursion(n - 1, n * acc)
Factorial.tail_recursion(5)
尾遞歸的調(diào)用過程大致是
tail_recursion(5, 1)
tail_recursion(4, 5)
tail_recursion(3, 20)
tail_recursion(2, 60)
tail_recursion(1, 120)
120
編譯器會(huì)根據(jù)尾遞歸的方式笼踩，進(jìn)行優(yōu)化逗爹，使得遞歸調(diào)用的時(shí)候并不會(huì)向線性遞歸那樣堆積內(nèi)存。就和循環(huán)迭代的效果一樣嚎于。這樣也是函數(shù)式編程語言處理迭代的問題掘而。
尾遞歸優(yōu)化主要是對(duì)棧內(nèi)存空間的優(yōu)化, 這個(gè)優(yōu)化是O(n)到O(1)的; 至于時(shí)間的優(yōu)化, 其實(shí)是由于對(duì)空間的優(yōu)化導(dǎo)致內(nèi)存分配的工作減少所產(chǎn)生的, 是一個(gè)常數(shù)優(yōu)化, 不會(huì)帶來質(zhì)的變化挟冠。
那么看看scheme的實(shí)現(xiàn)方式
(define (tail-recursion n acc)
(if (= n 1)
acc
(tail-recursion (- n 1) (* n acc))))
(tail-recursion 5 1)
看了兩個(gè)例子，尾遞歸還是很好理解镣屹。形式上盤的就是最后一個(gè)return的時(shí)候圃郊，是單純的返回一個(gè)函數(shù)調(diào)用价涝，還是返回函數(shù)計(jì)算女蜈。即
- 尾遞歸返回
return cls.tail_recursion(n - 1, n * acc)只返回純函數(shù) - 普通遞歸返回
return n * cls.recursion(n - 1)返回函數(shù)和別的表達(dá)式運(yùn)算
函數(shù)式語言基本上都支持尾遞歸，用來做迭代功能色瘩，下面是elixir的例子
defmodule Factorial do
def tail_recursion(n, acc) when n == 1 do
acc
end
def tail_recursion(n, acc \\ 1) do
tail_recursion(n-1, n * acc)
end
end
IO.puts Factorial.tail_recursion(5)
迭代與遞歸
函數(shù)式編程語言伪窖，通常沒有其他語言所謂的循環(huán)關(guān)鍵字。需要迭代的時(shí)候居兆，可以用遞歸實(shí)現(xiàn)覆山。最初也比較難理解遞歸如何實(shí)現(xiàn)？實(shí)際上泥栖，處理循環(huán)的時(shí)候簇宽，都是通過循環(huán)因子控制循環(huán)條件，在循環(huán)體內(nèi)進(jìn)行處理計(jì)算吧享。遞歸也可以這樣做魏割，遞歸的條件終止的條件可以用遞歸的參數(shù)設(shè)置。
下面演示給一個(gè)列表钢颂，遍歷每一個(gè)列表的元素钞它，并給每個(gè)元素的值翻倍。同樣使用三種語言代表：
class Double(object):
@classmethod
def recursion(cls, lst):
if not lst:
return []
else:
head, tail = lst.pop(0), lst
return [2 * head] + cls.recursion(lst)
@classmethod
def tail_recursion(cls, lst, new_lst=[]):
if not lst:
return new_lst
else:
head, tail = lst.pop(0), lst
new_lst.append(2 * head)
return cls.tail_recursion(tail, new_lst)
Double.recursion([1, 2, 3, 4, 5])
Double.tail_recursion([1, 2, 3, 4, 5])
Scheme
(define (recursion lst)
(if (null? lst)
`()
(cons (* 2 (car lst)) (recursion (cdr lst)))))
(define (tail-recursion lst new-lst)
(if (null? lst)
new-lst
(tail-recursion (cdr lst) (append new-lst (list (* 2 (car lst)))))))
(recursion (list 1 2 3 4 5))
(tail-recursion (list 1 2 3 4 5) `())
Elixir
defmodule Double do
def recurssion([head|tail]) do
[2 * head | recurssion(tail)]
end
def recurssion([]) do
[]
end
def tail_recursion([head|tail], new_list) do
new_list = new_list ++ [2 * head]
tail_recursion(tail, new_list)
end
def tail_recursion([], new_list) do
new_list
end
end
Double.recurssion([1, 2, 3, 4, 5])
Double.tail_recursion([1, 2, 3, 4, 5], [])
了解遞歸和尾遞歸之后殊鞭，另外一個(gè)需要了解就是并不是每個(gè)語言都支持尾遞歸遭垛。上述的 python就不支持。Python使用尾遞歸操灿，在數(shù)據(jù)量稍大的時(shí)候會(huì)溢出锯仪。此外，像 Scheme和Elixir這些語言則很好的支持趾盐。當(dāng)需要在遍歷的時(shí)候?qū)戇壿嬄牙遥梢猿橄蟪鲞壿嫗橐粋€(gè)個(gè)函數(shù)，更有利于代碼的模塊化和復(fù)用谤碳。
總結(jié)一下溃卡，普通遞歸過程是函數(shù)調(diào)用，涉及返回地址蜒简、函數(shù)參數(shù)瘸羡、寄存器值等壓棧等，而尾遞歸壓棧操作并無必要搓茬，不會(huì)有中間結(jié)果需要緩存犹赖。通常是語言層面是否支持队他，編譯器或解釋器中進(jìn)行優(yōu)化。
參考資料
