版權申明：本文為博主窗戶(Colin Cai)原創，歡迎轉帖。如要轉貼，必須注明原文網址 http://www.rzrgm.cn/Colin-Cai/p/11774213.html 作者：窗戶 QQ/微信：6679072 E-mail：6679072@qq.com
尾遞歸
這篇文章，我們講尾遞歸。在遞歸中，如果該函數的遞歸形式表現在函數返回的時候，則稱之為尾遞歸。
舉個簡單的例子，用偽碼如下：
function Add(a, b)
if a = 0
return b
return Add(a-1, b+1)
end
上面這個函數實際上是兩個數的加法，簡單起見，只考慮非負整數，后面敘述具體語言總是會以這個函數為例子。所有的return部分都是不再依賴于遞歸，或者是返回Add函數，其參數的計算不再依賴于遞歸，典型的尾遞歸。
上述代碼很容易用循環表示：
function Add(a, b)
while True
if a = 0
return b
end
a <= a-1
b <= b+1
end
end
所有的尾遞歸都可以用循環表示，只需要把傳入的參數當成是狀態，運算的過程當成是狀態的轉換。
比如Add(3,0)的計算就經過
3,0
2,1
1,2
0,3
這樣的狀態轉換。
函數的計算會維護一個棧，每當遇到函數調用會記錄當前運行的狀態，如此在函數返回的時候可以恢復上下文。
比如，對于Fibonacci數列，偽碼如下：
function fib(n)
if n < 3
return 1
end
return fib(n-1)+fib(n-2)
end
我們計算fib(4)，棧大致如下：
fib(4)
=>
fib(4)
fib(3)
=>
fib(4)
fib(3)
fib(2)
=>
fib(4)
fib(3)
fib(2) 1
=>
f(4)
f(3) 1+
=>
f(4)
f(3) 1+
f(1)
=>
f(4)
f(3) 1+
f(1) 1
=>
f(4)
f(3) 2
=>
f(4) 2+
=>
f(4) 2+
f(2)
=>
f(4) 2+
f(2) 1
=>
f(4) 3
=>
3
而作為尾遞歸，我們計算Add(3,0)，棧可能是如下過程：
Add(3,0)
=>
Add(3,0)
Add(2,1)
=>
Add(3,0)
Add(2,1)
Add(1,2)
=>
Add(3,0)
Add(2,1)
Add(1,2)
Add(0,3)
=>
Add(3,0)
Add(2,1)
Add(1,2)
Add(0,3) 3
=>
Add(3,0)
Add(2,1)
Add(1,2) 3
=>
Add(3,0)
Add(2,1) 3
=>
Add(3,0) 3
=>
3
對于Add函數，以上棧的長度與計算量成正比。如此，意味著計算量越大所需要的棧越大，甚至導致超過最大限制而無法運算。
同時我們發現，簡單的轉為循環表示的Add則沒有這個問題。
這里，可以采用一個編譯技術，就是尾遞歸優化，其一般情況是，如果一個函數的計算中遇到了完全轉化成另一個函數調用的情況，那么棧的當前函數部分的信息可以完全抹去，而替換為新的函數。如此處理下，此情況棧不會增長。
Add(3,0)的棧的過程如下：
Add(3,0)
=>
Add(2,1)
=>
Add(1,2)
=>
Add(0,3)
=>
3
尾遞歸優化給了我們一種迭代的方式，之所以研究它，在于函數式編程會用到它。
注：遞歸論區分遞歸和迭代(迭置)，和計算機上定義有一點區別，在此不深入。
C/C++
我們從底層的語言開始，首先還是上面的加法實現。為了讓范圍更大一點，便于觀察，我們使用unsigned long long類型。
/*add.c*/ unsigned long long add(unsigned long long a, unsigned long long b) { if(a==0ULL) return b; return add(a-1ULL,b+1ULL); }
再寫一個main來測試它，用命令行參數去獲得傳入add的兩個參數
#include <stdio.h> unsigned long long add(unsigned long long a, unsigned long long b); int main(int argc, char **argv) { unsigned long long a, b; sscanf(argv[1], "%llu", &a); sscanf(argv[2], "%llu", &b); printf("%llu\n", add(a,b)); return 0; }
用gcc編譯，
gcc add.c main.c -o a.out
運行一下，
./a.out 10000000 100000000
馬上發生短錯誤，直接崩潰。看來C語言作為底層語言沒必要支持這個啊？
于是我們開啟優化，
gcc -O2 add.c main.c -o a.out
然后運行一下
./a.out 10000000000000000 10000000000000000
立即得到我們想要的值而沒有發生崩棧
20000000000000000
看來……不對，1億億次迭代瞬間完成？
objdump反匯編一把，
00000000004006b0 <add>: 4006b0: 48 8d 04 37 lea (%rdi,%rsi,1),%rax 4006b4: c3 retq
……原來全被優化了，gcc現在還真強大，直接猜出語義，clang測一把也是如此。
這個并非我們想要的，我們得用其他手段去驗證(其實我們可以抽出部分優化選項來，但此處講的是驗證思路)。
此處借助我在《相互遞歸》中講的奇偶判斷，分三個函數，實現如下，
/*sub1.c*/ unsigned long long sub1(unsigned long long x) { return x - 1ULL; }
/*is_odd.c*/ unsigned long long sub1(unsigned long long x); int is_even(unsigned long long x); int is_odd(unsigned long long x) { if(x == 0ULL) return 0; return is_even(sub1(x)); }
/*is_even.c*/ unsigned long long sub1(unsigned long long x); int is_odd(unsigned long long x); int is_even(unsigned long long x) { if(x == 0ULL) return 1; return is_odd(sub1(x)); }
上述函數是單獨編寫，甚至，減1的操作也單獨用一個文件來實現。如此測試的原因，就在于，我們要排除掉整體優化的可能。
還需要寫一個main函數來驗證，
/*main.c*/ #include <stdio.h> int is_odd(unsigned long long x); int main(int argc, char **argv) { unsigned long long x; sscanf(argv[1], "%llu", &x); printf("%llu is %s\n", x, is_odd(x)?"odd":"even"); return 0; }
以上四個文件單獨編譯，開啟-O2優化選項(當然，其實main無所謂)
for i in sub1.c is_odd.c is_even.c main.c; do gcc -O2 -c $i; done
然后鏈接，
gcc sub1.o is_odd.o is_even.o main.o -o a.out
然后我們對一個很大的數來進行測試，
./a.out 10000000000
一會兒之后，程序打印出
10000000000 is even
以上可以證明，gcc/clang對于尾遞歸優化支持的挺好。實際上，很早之前大部分C語言編譯器就支持了這點，因為從技術上來看，并不是很復雜的事情。而C++也同理。
Python
Python實現add如下
def add(a, b): if a==0: return b return add(a-1, b+1)
計算add(1000,0)就崩棧了，顯然Python的發行是不支持尾遞歸優化的。
不過這里棧似乎小了點，可以用sys.setrlimit來修改棧的大小，這實際上是UNIX-like的系統調用。
有人用捕捉異常的方式讓其強行支持尾遞歸，效率當然是損失很多的，不過這個想法倒是很好。想起以前RISC大多不支持奇邊界存取值，比如ARM，于是在內核中用中斷處理強行支持奇邊界錯誤，雖然效率低了很多，但邏輯上是通過的。異曲同工，的確也是一條路，不過我還是更加期望Python在未來支持尾遞歸優化吧。
JavaScript
依然是用add測試，編寫以下網頁
<input type="text" id="in1" /> <input type="text" id="in2" /> <input type="button" id="bt1" onclick="test()" value="測試"/> <script type="text/javascript"> function add(a, b) { if (a==0) { return b; } return add(a-1, b+1); } function test() { a = parseInt(document.getElementById("in1").value); b = parseInt(document.getElementById("in2").value); try { alert(add(a,b)); } catch(err) { alert('Error'); } } </script>
就用1000000和0來測試，沒看到哪個瀏覽器不跳出Error的……據說v8引擎做好了，可是人家就不給你用……
Scheme
然后我們來看Scheme，按照Scheme的標準一向強行規定Scheme支持尾遞歸優化。
我們實現add函數如下
(define (add a b) (if (zero? a) b (add (- a 1) (+ b 1))))
實現更為復雜的奇偶判斷
(define (is-odd x) (if (zero? x) #f (is_even (- x 1)))) (define (is-even x) (if (zero? x) #t (is_odd (- x 1))))
使用Chez Scheme、Racket、guile測試，使用很大的數來運算，
然后使用top來觀測程序的內存使用情況，我們發現，雖然CPU占用率可能是100%，但內存的使用并不增加。就連guile這樣的一個小的實現都是如此，從而它們都是符合標準而對尾遞歸進行優化的。
Common Lisp
測完Scheme，再來測Scheme的本家兄弟，另外一種Lisp——Common Lisp
先用Common Lisp實現add，因為Common Lisp將數據和過程用不同的命名空間，導致代碼有點奇怪(似乎很不數學)
(defun add(a b) (if (zerop a) b (funcall #'add (- a 1) (+ b 1))))
使用clisp來運行
(add 10000 10000)
結果就
*** - Program stack overflow. RESET
因為沒有尾遞歸優化的規定，所以對于那種無限循環，Common Lisp只能選擇迭代才能保證不崩棧，比如使用do。使用do重新實現add如下
(defun add(a b) (do ((x a (- x 1)) (y b (+ y 1))) ((zerop x) y)))
如此，終于不崩棧了。但是似乎也改變了Lisp的味道，do顯然此處只能在設計編譯器、解釋器的時候就得單獨實現，雖然按理Lisp下這些都應該是宏，但是無論用宏如何將函數式編程映射為顯示的迭代，因為尾clisp遞歸優化不支持，則無法和系統提供的do一樣。
sbcl是Common Lisp的另外一個實現，在這個實現中，我們使用第一個add函數的版本，沒有發生崩棧。我們再來實現一下奇偶判斷
(defun is-odd(x) (if (zerop x) '() (funcall #'is-even (- x 1)))) (defun is-even(x) (if (zerop x) t (funcall #'is-odd (- x 1))))
計算
（is-even 1000000000)
過了幾秒，返回了結果t，證明了sbcl對尾遞歸做了優化。也終于給了我們一個更為靠譜的Common Lisp的實現。
AWK
選擇一種腳本語言來測試這個問題，使用GNU awk來實現add
awk ' function add(a,b) { if(a==0) return b return add(a-1, b+1) } {print add($1, $2)}'
運行后，用top來觀測內存占用
輸入
100000000 1
讓其做加法
內存使用瞬間爆發，直到進程被系統KO。
話說，awk沒有對尾遞歸優化也屬正常，而且對于內存的使用還真不節制，超過了我的想象。不過這也與語言的目的有關，awk本就沒打算做這類事情。
Haskell
直接上如下Haskell程序來描述奇偶判斷
is_even x = if x==0 then True else is_odd (x-1) is_odd x = if x==0 then False else is_even (x-1) main = print (is_even 1000000000)
用ghc編譯運行，輸出True，用時33秒。
Haskell不虧是號稱純函數式編程，尾遞歸優化無條件支持。
Prolog
本不想測prolog，因為首先它并沒有所謂的函數，靠的是謂詞演化來計算，推理上的優化是其基本需求。尾遞歸本不屬于Prolog的支持范疇，當然可以構造類似尾遞歸的東西，而且Prolog當然可以完成，不會有懸念。
比如我們實現奇偶判斷如下：
is_even(0, 1). is_even(X, T) :- M is X-1, is_odd(M, T). is_odd(0, 0). is_odd(X, T) :- M is X-1, is_even(M, T).
查詢
?- is_even(100000000,S),write(S),!.
得到
1
Erlang
先寫一個model包含add/even/odd三個函數，
-module(mytest). -export([add/2,even/1,odd/1]). add(A,B)->if A==0->B;true->add(A-1,B+1) end. even(X)->if X==0->true;true->odd(X-1) end. odd(X)->if X==0->false;true->even(X-1) end.
加載模板，并測試如下
1> c(mytest).
{ok,mytest}
2> mytest:add(1000000000,1000000000).
2000000000
3> mytest:even(1000000000).
true
4> mytest:odd(1000000000).
false
顯然，Erlang對尾遞歸支持很好。
golang
編寫add的實現如下
package main import "fmt" func add(a int, b int) int { if (a==0) { return b; } return add(a-1,b+1); } func main() { fmt.Println(add(100000000, 0)) }
運行
go run add.go
馬上崩潰
Lua
Lua的作者和JS的作者一樣是Lisp的粉絲，Lua的后期設計(從Lua4)據說參考了Scheme。
function odd(x) if (x==0) then return false end return even(x-1) end function even(x) if (x==0) then return true end return odd(x-1) end print(odd(io.read()))
運行
echo 1000000000 | lua5.3 x.lua
過程中，觀察內存沒有明顯變化，之后打印出了false。
看來，至少參考了Scheme的尾遞歸優化。
Ruby
Ruby的作者松本行弘也是Lisp的粉絲，當然，我想大多數編程語言的作者都會是Lisp的粉絲，因為它會給人很多啟發。
實現奇偶判斷如下：
#!/usr/bin/ruby def odd(x) if x == 0 return 0 end return even(x-1) end def even(x) if x == 0 return 1 end return odd(x-1) end puts even gets.to_i
然而，數字大一點點，就崩棧了。Ruby并不支持尾遞歸優化。
尾聲
測了這些語言以及相應的工具，其實還是在于函數式編程里，尾遞歸實現的迭代是我們經常使用的手段，編譯器/解釋器的支持就會顯得很重要了。再深一步，我們會去想想，編譯器/解釋器此處該如何做，是否可以對現有的設計進行修改呢？或者，對該語言/工具的未來懷著什么樣的期待呢？再或者，如果我們自己也設計一種編程語言，會如何設計這種編程語言呢？……
浙公網安備 33010602011771號