Clojure 学习笔记 :10 美妙的递归
Clojure 零基础 学习笔记 递归 尾递归
递归，或者说函数的递归，在程序设计语言里指的是函数内部又调用函数本身的用法。
一个经典的例子就是阶乘的计算。我们来分析一下，数学上的阶乘是什么意思呢？简单来说，N 的阶乘就等于 1 * 2 * 3 ... * N 的值。如果不使用递归，我们可以先搞一个从 1 到 N 的数列，然后把它们相乘。
我们可以用 reduce 函数来实现：
(defn factorial
[number]
(reduce * (range 1 (inc number)))) ;; 注意这里 range 的第二个参数要加一。
也可以用 apply 函数实现：
(defn factorial
[number]
(apply * (range 1 (inc number))))
apply 函数可以把一个序列展开作为某个函数的参数：
(apply * [1 2 3])
;; 等价于
(* 1 2 3)
但是，当你试图计算 100 的阶乘的时候，就会出现问题。为什么呢？因为 Clojure 中整数 字面量[1] 默认为 int 类型，而 100 的阶乘已经大于 int 类型所能表达的最大值。为了解决这个问题，Clojure 提供了可以支持无限精度的 “大数” 字面量。你只需要在整数字面量后面加上大写的 N，就可以把它变为可支持 无限范围[2] 的 “大整数”。顺带一提，如果在小数后加上大写的 M，就可以把它变为无限精度的小数。大数类型和普通类型进行运算，结果自动变成大数类型。
(defn factorial
[number]
(reduce * (range 1N (inc number))))
=> (factorial 100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000N
说了半天，还是没有说到本次的主题。如何使用递归来解决阶乘的问题呢？首先，我们可以观察出，N 的阶乘其实等于 N-1 的阶乘的值 再乘以 N。如果可以得出 N-1 的阶乘的值，计算出 N 的阶乘就很简单了。那 N-1 的阶乘等于多少呢？它等于 N-2 的阶乘 乘以 N-1 …… 不行太绕了。
其实仔细想一下，N-1 的阶乘的值，不也是我们这个阶乘函数的 “责任范围” 么？如果假装我们的函数已经做好了，那我们直接调用我们的阶乘函数不就好了？这么神奇么？是的，就是这么神奇。
代码看起来还是很清晰的：
(defn factorial-recursive
[number]
(* number (factorial-recursive (dec number)))) ;; 假装能计算 N-1 的阶乘
看起来很完美。但是，如果你真的这么做了，分分钟系统就罢工了😂。
为什么呢？其实在函数里面我们调用自己的时候，相当于又重新执行了这个函数，系统会记下来当前的情况，然后就去新世界冒险了，但是这个新世界函数里面又调用了新函数，子子孙孙无穷尽，根本停不下来了。所以到最后系统资源耗尽，就崩溃了。
怎么办呢？我们要想办法让它停下来。怎么停下来呢？我们知道，1 的阶乘的值 就是 1，计算到 1 的时候，就可以直接返回 1 这个值了：
(defn factorial-recursive
[number]
(if (= 1 number)
1N
(* number (factorial-recursive (dec number)))))
这样，当层层调用到 1 的时候，就会停下，然后层层返回，最终得到结果。
所以“递归”，最后要“归”。
我们总结一下写出一个递归的要点：
- 找到函数内需要执行函数自己的地方
- 找到结束条件，避免无限递归
你可能会听到许多关于递归的 “诋毁”，比如递归效率极其缓慢，递归容易引起堆栈溢出等等。其实他们说的也不算错，不过，也不算全对。只需要做一点小小的手段，递归的速度和空间占用就可以媲美非递归形式，有时候甚至比非递归形式更快更好！
这种手段叫做尾递归优化。
什么叫尾递归优化呢？首先我们要知道什么是尾递归。
从字面上看，尾递归就是在尾巴处进行递归，这个尾巴的意思指的是，函数的最后一行（也就是函数返回值的位置）。在最后一行调用自己来递归，系统本来是要记录调用的情况方便调用完毕之后能找到回来的路来执行下面的代码，但是由于我们是在最后一行进行递归，下面已经没有代码来执行了，系统也就不用保存什么记录了，也就不会占用空间。
但是我们的阶乘函数，最后一行不仅要执行递归，而且还需要乘上一个数字，系统不得不保留那个数字，以便递归返回时进行乘法，怎么才能既保留那个数字，又能让最后一行只有递归调用呢？
答案是：把必要的数据保存在参数中，以参数的形式传递给下一次递归。我们来看一下尾递归形式的阶乘函数：
(defn factorial-tail-recursive
[number result]
(if (= 1 number)
result
(factorial-recursive (dec number) (* (bigint result) number)))) ;; 使用 bigint 函数和在整数字面量后加大写 N 的效果一样，可以把一个整型变量变成大整型
=> (factorial-tail-recursive 4 1)
24N
我们来观察一下，最后一行的确只有递归调用了，但是多的这个参数是什么意思呢？其实它用来保存每一步的结果，这里我们利用了乘法的交换律，以及任一个数字乘以 1 都等于它本身这两个性质。使用这个函数的时候，第二个参数要为 1。每次递归都会把 number 乘上这个数字，其实相当于倒着乘了一遍。最后递归终止的位置，直接返回这个结果就可以了。
这样是不是就算优化完成了？很抱歉还差最后一步。我们要把尾递归函数位置改为 recur，也就是递归的英文 recursive 的缩写。
(defn factorial-tail-recursive
[number result]
(if (= 1 number)
result
(recur (dec number) (* (bigint result) number))))
这样，一个满血版本，不会造成堆栈溢出，无限精度的，阶乘递归函数就完成了。
为什么要搞一个 recur 出来呢？Clojure 并没有强制要求 recur 必须放在末尾，如果你把 recur 放在其它地方，它会立即递归，而且递归完毕之后不会继续执行下面的代码。这样就提供了更多的灵活性。
递归在函数世界里面非常常见，它不仅表达清晰，代码简练，而且利用尾递归优化，可以让递归形式也拥有很高的效率。但尾递归要求你能用一个合理的手段把信息以参数的形式传递给下次递归，这就增加了编写递归的难度。如果你没有超凡的智力，也没有扎实的数学基础，那就多看例子，多写代码。代码量提高，才有充足的经验供你写出漂亮的递归来。
参考博客：
zx-dennis《详解Clojure的递归(上）—— 直接递归及优化》
zx-dennis《Clojure的recur尾递归优化探秘》
p.s.: 本文开头的引用也是一个 “递归” 引用。(灵感来自 什么是递归？)
