详解clojure递归（上）
详解clojure递归（下）
这篇blog拖到现在才写，如果再不写，估计就只有上篇没有下篇了，趁周末写一下。
上篇提到了Clojure仅支持有限的TCO，不支持间接的TCO，但是有一类特殊的尾递归clojure是支持，这就是相互递归。且看一个例子,定义两个函数用于判断奇数偶数：
这里使用declare做前向声明，不然在定义my-odd?的时候my-even?还没有定义，导致出错。可以看到，my-odd?调用了my-even?，而my-even?调用了my-odd?，这是一个相互递归的定义:如果n为0，那肯定不是奇数，否则就判断n-1是不是偶数，反之亦然。
这个递归定义看起来巧妙，但是刚才已经提到clojure通过recur支持直接的TCO优化，这个相互递归在大数计算上会导致堆栈溢出：
怎么解决呢？一个办法是转化成一个直接递归调用，定义一个parity函数，当偶数的时候返回0，当奇数的时候返回1：
parity是直接的尾递归，并且使用了recur优化，重新定义my-odd和my-even就很简单了：
但是这样的方式终究不是特别优雅，相互递归的定义简洁优雅，有没有什么办法保持这个优雅的定义并且避免堆栈溢出呢？答案是trampoline，翻译过来是弹簧床，查看trampoline函数文档：
看到 trampoline利用recur做了尾递归优化，原有的my-odd?和my-even?需要做一个小改动，就可以利用 trampoline来做递归优化了：
唯一的改动就是函数的末尾行前面加了个#，将递归调用修改成返回一个匿名函数了，使用 trampoline调用my-even?和my-odd?不会再堆栈溢出了：
详解clojure递归（下）
这篇blog拖到现在才写，如果再不写，估计就只有上篇没有下篇了，趁周末写一下。
上篇提到了Clojure仅支持有限的TCO，不支持间接的TCO，但是有一类特殊的尾递归clojure是支持，这就是相互递归。且看一个例子,定义两个函数用于判断奇数偶数：
(declare my
-
odd
?
my
-
even
?
)
(defn my - odd ? [n]
( if ( = n 0 )
false
(my - even ? (dec n))))
(defn my - even ? [n]
( if ( = n 0 )
true
(my - odd ? (dec n))))
(defn my - odd ? [n]
( if ( = n 0 )
false
(my - even ? (dec n))))
(defn my - even ? [n]
( if ( = n 0 )
true
(my - odd ? (dec n))))
这里使用declare做前向声明，不然在定义my-odd?的时候my-even?还没有定义，导致出错。可以看到，my-odd?调用了my-even?，而my-even?调用了my-odd?，这是一个相互递归的定义:如果n为0，那肯定不是奇数，否则就判断n-1是不是偶数，反之亦然。
这个递归定义看起来巧妙，但是刚才已经提到clojure通过recur支持直接的TCO优化，这个相互递归在大数计算上会导致堆栈溢出：
user
=>
(my
-
odd
?
10000
)
java.lang.StackOverflowError (NO_SOURCE_FILE: 0 )
user=> (my-even? 10000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)
java.lang.StackOverflowError (NO_SOURCE_FILE: 0 )
user=> (my-even? 10000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)
怎么解决呢？一个办法是转化成一个直接递归调用，定义一个parity函数，当偶数的时候返回0，当奇数的时候返回1：
(defn parity [n]
(loop [n n par 0 ]
( if ( = n 0 )
par
(recur (dec n) ( - 1 par)))))
user=> (parity 3)
1
user=> (parity 100)
0
user=> (parity 10000)
0
user=> (parity 10001)
1
(loop [n n par 0 ]
( if ( = n 0 )
par
(recur (dec n) ( - 1 par)))))
user=> (parity 3)
1
user=> (parity 100)
0
user=> (parity 10000)
0
user=> (parity 10001)
1
parity是直接的尾递归，并且使用了recur优化，重新定义my-odd和my-even就很简单了：
(defn my
-
even
?
[n] (
=
0
(parity n)))
(defn my - odd ? [n] ( = 1 (parity n)))
(defn my - odd ? [n] ( = 1 (parity n)))
但是这样的方式终究不是特别优雅，相互递归的定义简洁优雅，有没有什么办法保持这个优雅的定义并且避免堆栈溢出呢？答案是trampoline，翻译过来是弹簧床，查看trampoline函数文档：
user
=>
(doc trampoline)
-------------------------
clojure.core / trampoline
([f] [f & args])
trampoline can be used to convert algorithms requiring mutual
recursion without stack consumption. Calls f with supplied args, if
any. If f returns a fn, calls that fn with no arguments, and
continues to repeat, until the return value is not a fn, then
returns that non - fn value. Note that if you want to return a fn as a
final value, you must wrap it in some data structure and unpack it
after trampoline returns.
简单来说
trampoline接收一个函数做参数并调用，如果结果为函数，那么就递归调用函数，如果不是，则返回结果，主要就是为了解决相互递归调用堆栈溢出的问题，查看
trampoline的定义：-------------------------
clojure.core / trampoline
([f] [f & args])
trampoline can be used to convert algorithms requiring mutual
recursion without stack consumption. Calls f with supplied args, if
any. If f returns a fn, calls that fn with no arguments, and
continues to repeat, until the return value is not a fn, then
returns that non - fn value. Note that if you want to return a fn as a
final value, you must wrap it in some data structure and unpack it
after trampoline returns.
(defn trampoline
([f]
(let [ret (f)]
( if (fn ? ret)
(recur ret)
ret)))
([f]
(let [ret (f)]
( if (fn ? ret)
(recur ret)
ret)))
看到 trampoline利用recur做了尾递归优化，原有的my-odd?和my-even?需要做一个小改动，就可以利用 trampoline来做递归优化了：
(declare my
-
odd
?
my
-
even
?
)
(defn my - odd ? [n]
( if ( = n 0 )
false
#(my - even ? (dec n))))
(defn my - even ? [n]
( if ( = n 0 )
true
#(my - odd ? (dec n))))
(defn my - odd ? [n]
( if ( = n 0 )
false
#(my - even ? (dec n))))
(defn my - even ? [n]
( if ( = n 0 )
true
#(my - odd ? (dec n))))
唯一的改动就是函数的末尾行前面加了个#，将递归调用修改成返回一个匿名函数了，使用 trampoline调用my-even?和my-odd?不会再堆栈溢出了：
user
=>
(trampoline my
-
odd
?
10000000
)
false
user => (trampoline my - even ? 10000 )
true
user => (trampoline my - even ? ( * 1000 1000 ))
true
文章转自庄周梦蝶 ，原文发布时间 2010-08-22false
user => (trampoline my - even ? 10000 )
true
user => (trampoline my - even ? ( * 1000 1000 ))
true
