- 手艺 tags:
- clojure published: true comments: true
clojure是函数是编程语言，本身没有循环的语法。要实现类似循环的效果，需要用递归来实现。比如计算从1加到n的和这样一个函数：
[cc lang="lisp"]
(defn addup
([limit] (addup limit 0 0))
([limit current sum]
(if (< limit current)
sum
(addup limit (+ 1 current) (+ current sum)))))
[/cc]
调用
(addup 10)
可以得到55
但是调用
(addup 50000)
不出意外，出现了StackOverflowException， 这是递归典型的错误。
为此，需要进行优化。尾递归优化是指如果递归满足一定条件，编译器可以将递归展开，避免出现栈溢出的问题。这里的条件，就是递归的最后一次调用是否是其本身，比如上面的代码，最后一次操作仍然是addup，即满足尾递归的条件，而如果同样的代码写成：
[cc lang="lisp"]
(defn addup2
([limit] (addup2 limit 0))
([limit current]
(if (< limit current)
0
(+ current (addup2 limit (+ current 1))))))[/cc]
最后一个操作是+，不满足尾递归循环，无法进行优化。
clojure默认不进行尾递归优化，需要使用关键字recur来保证优化，把第一段代码写成：
[cc lang="lisp"]
(defn addup
([limit] (addup limit 0 0))
([limit current sum]
(if (< limit current)
sum
(recur limit (+ 1 current) (+ current sum)))))
[/cc]
社区的解释是，如果程序员在无法进行尾递归优化的代码中使用recur会发生报错，这样有助于他们发现代码中潜在的缺陷。
在第二段代码中使用recur，会得到异常：
java.lang.UnsupportedOperationException: Can only recur from tail position
此外，clojure提供loop函数简化书写：
[cc lang="lisp"]
(defn addup3
([limit]
(loop [current 0 sum 0]
(if (< limit current)
sum
(recur (+ current 1) (+ current sum))))))
[/cc]
这种写法同样可以应用尾递归优化而不会导致栈溢出。
The post is brought to you by lekhonee v0