探索那些不常见的控制流（2）

尾（巴）递归，尾调用优化，尾递归优化
tailrecursion, tailcall optimization and tailreursion eliminate

最早学scheme的时候就玩过尾递归（tailrecursion），不过当时只是在形式上玩了下，也大概理解尾递归可以让编译器重用函数调用栈，而不会导致函数调用栈溢出发生，同时模糊的说这种写法可以和迭代的效率相当。我们一群人学scheme的时候，只是皮毛的把SICP的前2章的内容和题目看掉、做掉。那段时间我狂看C++的那些书籍，学STL我就直接硬着头皮大致看掉《STL源码剖析》（我才发现要学一个东西未必要按部就班从Prime开始，直接跳过Prime书籍直接看深入一点的书籍也是大有好处的，不用先非常熟悉使用，过了很久之后才想起来去看下源码，才发现之前很多用法实际上多绕了很多弯路，MFC没用过，但我看过《MFC深入浅出》前几章，大概知道那些繁杂的要点在哪，这样就不会心里有惧怕感。）；学模板我就看了《The C++ Template》这书，这样就对那些特化、偏特化、typename，template template class，编译时多态（元编程，MetaProgram）等概念有比Prime系统性的一些了解，后面还粗略看了《Morden C++ Template》，知道boost和loki；学C++运行时多态，我看了《Internal C++ Object Model》，这样就知道了class对象的内存分布，也就是虚函数表是最重要的，对象的构造、析构等也与内存分布息息相关，而且虽然不学COM，但知道COM要做ABI也是要知道C++的内存分布的，《COM本质论》前几章也在讲这个。SICP的习题都是一环扣一环，后面的习题直接给予前面的习题来继续做，这样我印象很深的是，抽象是如何被一步步封装起来的，对于每道习题，只要之前习题已经搭建的那些抽象（函数）是坚实的，就可以被用来组合新的抽象，这样我对于「任何软件问题都可以通过添加抽象层解决」这句话就有深入一点的理解，并且印象深刻。scheme由于概念简洁，function是一等公民，所以你会一直专注在解决问题本上上，而不用像C++那样一个又一个特性让你话费大把时间去学习和积累。函数式编程一些重要的概念：惰性求值、无副作用、无状态、不变性等基本概念都深入到我脑子里，以后我用其他语言的时候会不断重新发现这些概念。

想起来之前的那些事就顺便多写了这些，最近开始系统性重新学习和发现那些以前有些清晰有些模糊的概念：tailrecursion, tailcalloptimization, tailrecursioneliminate, continuation passing style, call-with-current-continuation,closure,coroutine,concept, constraint template arguments, lambda, recursion function等等。我想一边把这些编程语言相关的外在概念都梳理一遍，同时系统性学习编译原理、类型理论，再结合实战研究编程语言的实现，希望把这个角落清扫一遍。

恩，本系列以小步迭代方式进行。本节实际上是从下面页面的代码片段拿过来注释了下尾巴递归的概念。

http://c2.com/cgi/wiki?TailRecursion

#include <stdio.h>
#include <stdlib.h>
/**
 *非尾巴递归，return的时候需要做调用自己和一次乘法
 */
int factorial0(int n) {
    if (n == 0) return 1;
    return n * factorial0(n - 1);
}
/**
 *尾巴递归，return的时候只做一件事：递归调用自己
 */
int factorialimpl(int n, int accumulator) {
 if (n == 0) return accumulator;
 return factorialimpl(n - 1, n * accumulator);
}
int factorial1(int n) {
    return factorialimpl(n, 1);
}
/**
 *如果编译器能够识别并为尾巴递归做优化，则尾巴递归
 *等价于如下代码，不需要反复进入和退出嵌套的调用栈
 */
int factorial2(int n, int accumulator) {
 beginning:
 if (n == 0) return accumulator;
 else {
   accumulator *= n;
   n -= 1;
   goto beginning;
 }
}
/**
 *因此，尾巴递归的性能将和下面的迭代等价
 */
int factorial3(int n, int accumulator) {
    while (n != 0) {
      accumulator *= n;
      n -= 1;
    }
    return accumulator;
}

/**
 *这就是尾巴递归的故事，用C语言描述
 */
int main(){
 return 0;
}

上面的c代码演示了什么是尾巴递归，尾巴递归必须在函数返回前只做一件事，那就是递归调用自己。尾巴递归调用的重点在于递归调用返回到上一层调用栈的时候，上一层调用栈并不需要利用这个返回值做点什么事（否则，上层调用栈就必须保留栈上下文），而是直接返回给上上层调用栈。那么对于一定要对递归调用结果「做点什么事」的需求来说，就必须把要参与「做点什么事」的那些数据和函数传递给下层调用栈，比如这个例子里通过accumulator把结果传递给递归调用函数。

那么尾巴递归调用就保证了在尾巴递归的时候不需要保留上层函数调用栈上下文。所以如果编译器能识别尾巴递归调用，则可以对尾巴递归调用做「tailrecursion eliminate」，也就是例中的示意代码。消除了递归调用，从而把递归变成迭代。但这个前提是编译器会帮你做这件事，否则就算你写的代码是尾巴递归调用，但编译器不做「tailrecursion eliminate」的话，则没有这些福利。scheme、lua等语言都有对尾巴递归调用做消除。

进一步的，如果一个函数调用虽然不是经典的「tailrecursion」，但是在return之前只做一件事，就是调用某个其他子过程。则上层函数调用栈也不需要保存，则这个时候编译器可以做「tailcall optimization」，也就是尾调用优化。我们来下下例子：

http://c2.com/cgi/wiki?TailCallOptimization

/**
 *进一步的，尾调用优化
 */
int bar(int a){
     printf("bar called with arg %d\n", a);
     return a * a;
}
int foo(int b){
     return bar(b * b);//函数返回前只做一件事，调用只过程，并且把b*b的结果传入到子过程
}

/**
 *然而，这个例子里，foo的栈如果被优化掉，则a的生命周期
 *被破坏，所以用栈上变量a是不安全的。
 */
int bar(int *b){
     return *b * 10;
}
int foo(){
     int a = 5;
     return bar(&a);
}