編程很復(fù)雜，編程也很簡單。簡單的邏輯，通過代碼組織，就可以變成復(fù)雜程序或者系統(tǒng)。以前學(xué)物理的時候，老師就說考試的物理題其過程是相當(dāng)復(fù)雜的（簡單的就沒有必要考了）。解題方法眾多，分解法即是一個行之有效的方式。復(fù)雜的過程經(jīng)過分解，會變成簡單的定理。如同螺絲，輪胎，玻璃都很簡單，卻能組合而成復(fù)雜的汽車。

編程也類似，核心哲學(xué)甚至簡單得令人發(fā)指，其一是指針，其二是遞歸。深入理解者兩個概念，很多復(fù)雜的系統(tǒng)或者設(shè)計(jì)，都會化繁為簡，一目了然。

遞歸

遞歸，一個函數(shù)在內(nèi)部調(diào)用自己，就是遞歸。遞歸在生活中也很常見，例如我們的眼睛，你看對方的眼睛，對方的眼睛里面有你，而那里面那個你又有她，無限循環(huán)。再比如，當(dāng)你拿著一面鏡子，對著另外一面鏡子的時候，就會發(fā)現(xiàn)鏡子之中有你手指的鏡子，等等。

12903486_211n.jpg

尾遞歸

函數(shù)中可以調(diào)用自己成為遞歸，也可以在末尾調(diào)用別的函數(shù)。如果一個函數(shù)里的最后一個動作是一個函數(shù)調(diào)用的情形：即這個調(diào)用的返回值直接被當(dāng)前函數(shù)返回的情形。這樣的調(diào)用為尾調(diào)用。如果是尾調(diào)用自己，即為尾遞歸。

尾遞歸是一種形式, 這種形式表達(dá)出的概念可以被某些編譯器優(yōu)化. 尾遞歸的特殊形式?jīng)Q定了這種遞歸代碼在執(zhí)行過程中是可以不需要回溯的(通常的遞歸都是需要回溯的). 如果編譯器針對尾遞歸形式的遞歸代碼作了這種優(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）中簡單的演示了這個調(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)用之后，會繼續(xù)調(diào)用自身，并在棧里堆積內(nèi)存。scheme的解法也很簡單：

#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

編譯器會根據(jù)尾遞歸的方式，進(jìn)行優(yōu)化，使得遞歸調(diào)用的時候并不會向線性遞歸那樣堆積內(nèi)存。就和循環(huán)迭代的效果一樣。這樣也是函數(shù)式編程語言處理迭代的問題。

尾遞歸優(yōu)化主要是對棧內(nèi)存空間的優(yōu)化, 這個優(yōu)化是O(n)到O(1)的; 至于時間的優(yōu)化, 其實(shí)是由于對空間的優(yōu)化導(dǎo)致內(nèi)存分配的工作減少所產(chǎn)生的, 是一個常數(shù)優(yōu)化, 不會帶來質(zhì)的變化。

那么看看scheme的實(shí)現(xiàn)方式

(define (tail-recursion n acc)
  (if (= n 1)
      acc
      (tail-recursion (- n 1) (* n acc))))

(tail-recursion 5 1)

看了兩個例子，尾遞歸還是很好理解。形式上盤的就是最后一個return的時候，是單純的返回一個函數(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í)現(xiàn)。最初也比較難理解遞歸如何實(shí)現(xiàn)？實(shí)際上，處理循環(huán)的時候，都是通過循環(huán)因子控制循環(huán)條件，在循環(huán)體內(nèi)進(jìn)行處理計(jì)算。遞歸也可以這樣做，遞歸的條件終止的條件可以用遞歸的參數(shù)設(shè)置。

下面演示給一個列表，遍歷每一個列表的元素，并給每個元素的值翻倍。同樣使用三種語言代表：

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], [])

了解遞歸和尾遞歸之后，另外一個需要了解就是并不是每個語言都支持尾遞歸。上述的 python就不支持。Python使用尾遞歸，在數(shù)據(jù)量稍大的時候會溢出。此外，像 Scheme和Elixir這些語言則很好的支持。當(dāng)需要在遍歷的時候?qū)戇壿?，可以抽象出邏輯為一個個函數(shù)，更有利于代碼的模塊化和復(fù)用。

總結(jié)一下，普通遞歸過程是函數(shù)調(diào)用，涉及返回地址、函數(shù)參數(shù)、寄存器值等壓棧等，而尾遞歸壓棧操作并無必要，不會有中間結(jié)果需要緩存。通常是語言層面是否支持，編譯器或解釋器中進(jìn)行優(yōu)化。

參考資料

• 維基百科: 尾調(diào)用
• 知乎: 什么是尾遞歸
• 尾遞歸與Continuation