clojure recur

clojure是函数是编程语言，本身没有循环的语法。要实现类似循环的效果，需要用递归来实现。比如计算从1加到n的和这样一个函数：

(defn addup
([limit] (addup limit 0 0))
([limit current sum]
(if (< limit current)
sum
(addup limit (+ 1 current) (+ current sum)))))

调用

(addup 10)

可以得到55

但是调用

(addup 50000)

不出意外，出现了StackOverflowException，这是递归典型的错误。

为此，需要进行优化。尾递归优化是指如果递归满足一定条件，编译器可以将递归展开，避免出现栈溢出的问题。这里的条件，就是递归的最后一次调用是否是其本身，比如上面的代码，最后一次操作仍然是addup，即满足尾递归的条件，而如果同样的代码写成：

(defn addup2
([limit] (addup2 limit 0))
([limit current]
(if (< limit current)
0
(+ current (addup2 limit (+ current 1))))))

最后一个操作是+，不满足尾递归循环，无法进行优化。

clojure默认不进行尾递归优化，需要使用关键字recur来保证优化，把第一段代码写成：

(defn addup
([limit] (addup limit 0 0))
([limit current sum]
(if (< limit current)
sum
(recur limit (+ 1 current) (+ current sum)))))

社区的解释是，如果程序员在无法进行尾递归优化的代码中使用recur会发生报错，这样有助于他们发现代码中潜在的缺陷。

在第二段代码中使用recur，会得到异常：

java.lang.UnsupportedOperationException: Can only recur from tail position

此外，clojure提供loop函数简化书写：

(defn addup3
([limit]
(loop [current 0 sum 0]
(if (< limit current)
sum
(recur (+ current 1) (+ current sum))))))

这种写法同样可以应用尾递归优化而不会导致栈溢出。

The post is brought to you by lekhonee v0

Here comes the Sun