尾递归的迭代形式化

尾递归虽然在形式上是递归，但在逻辑上它和迭代等价

本文旨在阐述如上事实。我们先从阶乘这个喜闻乐见的例子开始：

递归

let rec fact n = 
    if n = 0 then 1
    else n*fact (n-1);;

上面就是一个很普通的递归写法，我们把问题划分为更小的子问题，然后通过操作子问题的解生成原问题的解。这是一种典型的递归策略，通俗易懂。这也使得递归结构成为几乎最容易理解的结构（如果你给出些许说明的话）。

尾递归

我们再看尾递归写法是怎么搞的：

let fact = 
	let rec f ans n = 
		if n = 0 then ans 
		else f (ans*n) (n-1) 
	in f 1;;

看起来好像并不复杂，但是也不直观（至少对于不了解尾递归写法的人来说）。我相信多数人都下意识的会认为这样的写法投机取巧，反人类，完全无法阅读。它真的是如此吗？

循环

我们再来看下C语言的for循环写出来什么样子：

int f(int n) {
    int ans = 1;
    while(True) {
        if(n == 0) return ans;
        else ans *= n, n -= 1;
    }
}

你觉得这段代码易于阅读吗？

如果你对C语言有基本的了解，我相信你能读懂这段代码。就像你了解for语句的结构一样，一旦你了解尾递归的结构，可读性和直观的也就伴随而来了。实际上，尾递归并非是一个trick，它在数学上表现得非常优雅，在事实上的“表达力”是超过循环的（你可以用更短的代码，表现更复杂的迭代，并且不失可读性）。

什么是尾递归(尾调用)

顾名思义，位于函数尾部的递归。这个尾，指的是调用的尾。也就是这个函数在递归调用之后，直接返回调用结果，不会再做更多操作。如果按照上面递归的思路来理解就是，“子”问题和原问题“等价”（并非真的等价，单向的），我们解决了子问题，也即解决了原问题。当然，我觉得这种理解丝毫不能帮助你理解和编写尾递归程序，因为构造一个等价问题往往是不直观的，而把原问题分解为多个子问题才是更自然的想法。所以递归带来直观并不适用于尾递归，这点上其实循环也并无不同。

向量化

我们改变思考问题的策略。我们不关注问题的本身，而只关注尾递归的形式。因为尾递归的过程，不会再返回调用函数进行额外操作，所以，我们把一个关于函数f的问题，映射到一个关于函数g的问题。

这里的技巧在于，我们把函数和它的参数看成一个向量。上面尾递归形式的阶乘的实际上就是：

当n>0，我们把向量f ans n映射到向量f (ans*n) (n-1)

实际上我们只是做了一些判断，然后把一个向量映射到另一个向量！然后在某个特定条件下，我们把向量映射到某个值，迭代结束。我们不断变换这个向量，直到它满足某个条件

参数向量

当f和g相同的时候，我们实际上就是对参数向量做变换。

形式化

iter args =
    if expr then res
    else iter args_new

条件部分除了条件语句还可以是模式匹配，可以有多分支。不管args有多长，分支有多少，迭代形式都会非常清晰。

可读性

尾递归不会因为它参数序列的变长而丢失它的可读性，因为它总是有着一致的迭代语义，层次分明。相比之下，传统的循环会随着变量的增多，变量会散落在循环各处。

直观性

你理解代码的结构，并不代表你真的理解代码真正在做的事情。对于复杂的算法来说，有什么办法能带来直观性吗？那自然是不会有的，你唯一能做的就是让算法描述和代码结构尽量一致，这样你就不需要变换形式就能理解了。

我并不觉得循环相比尾递归形式带来了更多的直观性，因为尾递归更加形式化，算法很容易用这种形式化的方式来表述（虽然有很多算法的伪码是用循环来表述的）。

尾调用优化(TCO)

因为尾调用的调用位于函数的尾部，所以函数直接把该调用的输出作为函数自己的输出。所以，保留当前函数的调用栈是毫无必要的。所以加入尾调用优化的的尾调用形式可以避免随着调用深度的增加导致栈溢出。

如果上面的形式化在逻辑上说明了尾调用的表达力的话，那么TCO的存在就使得尾调用就是事实上的迭代。它不会因为调用的深入导致调用栈溢出。

我们看到，其实尾递归（尾调用）不论在形式上还是逻辑上都比递归更加接近迭代，而且往往比循环语句表现的迭代更加形式化，结构也更加一致。反正我是找不到任何理由拒绝尾递归的使用，除非该语言没有提供TCO。