种种编程语言对尾递归的支撑
2019-11-18杂谈搜奇网55°c
A+ A-版权说明：本文为博主窗户(Colin Cai)原创，迎接转帖。如要转贴，必需说明原文网址 http://www.cnblogs.com/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并不支撑尾递归优化。
尾声
测了这些言语以及响应的东西，实在照样在于函数式编程里，尾递归完成的迭代是我们常常运用的手腕，编译器/诠释器的支撑就会显得很重要了。再深一步，我们会去想一想，编译器/诠释器此处该怎样做，是不是能够对现有的设想举行修正呢？或许，对该言语/东西的将来怀着什么样的期待呢？再或许，假如我们本身也设想一种编程言语，会怎样设想这类编程言语呢？……
