看了自己的动态记录，发现自己已经遗忘了曾经的自己，有一条动态，2013年的时候，我看了一篇关于尾递归的博文，那时候还只是一个初学者，胡乱评论了一下，作者希望我能写一篇博文发表一下自己的看法，当时没有写，然而现在却想写点什么总结一下，不保证说的没问题，只希望如果有像我当年一样的初学者看到，可以参考借鉴，或许能有些帮助，在此也感谢给我启发，教会我知识的陌生朋友们。
1. 递归就是一个函数直接或间接的自己调用自己，间接就是f0 -> f1 -> f0 ->f1这种，但也就是一个名词而已，并不神奇，它只是一个普普通通的函数调用，但由于自己调用自己这个特性，有一种自动化的力量，给它一个规则，它可以自动的持续运行下去，直到触发停止条件。一个递归函数就像是一个简单的计算机。
2. 所有的递归都可以用循环来替代，所有的循环也都可以用递归来替代，两者是等价的。
3. 递归是人脑的直接思维方式，循环是当前多数(我所知道的所有的)cpu的直接思维方式。
4. 对于cpu来讲，函数调用只是寄存器，内存，跳转等操作，如果不涉及额外栈空间使用（极简单函数的特殊情况），函数调用和循环的差别可能仅仅是使用的寄存器不同。
5. 递归可以把复杂的问题变得简单，是一种处理问题的模型。比如汉诺塔，快速排序，二叉树遍历和查找，如果学会使用递归这种思维方式思考问题，很多问题会变得很简单，大事化小，小事化了，每一步都是很简单的操作。
6. 正确的思维会使问题很简单，错误的思维会让人发懵，使用递归的思考方式是忘记调用的是自己，自己调用的是任意一个函数，那个函数有没有实现，是否实现得正确不是我现在要关心的事，我只要保证，在那个函数正确实现的前提下，我现在写的这个函数是没问题的，当我写完当前函数的时候，被调用的函数也就写完了(副产物)，因为它们是同一个，这有点像数学归纳法。
7. 正确的实现一个递归函数，需要保证有退出的条件，除非你是在写一个死循环，同时随着递归层数变深，问题逐渐简单化，规模逐渐缩小，或者是向退出条件逼近(收敛)。
8. 递归对栈空间的占用分两种，尾递归开启相应的优化之后不会导致栈空间使用不停扩大，非尾递归对栈空间的调用要看递归的层数，递归层数是可预测的，一般二分的递归(理想的情况，极端的情况二叉树会变成链表，这时候已经不是二分法了，但二叉树是可以事先保证平衡的)层数大约为log2(n)，30层函数调用使用的栈空间很少(使用超级庞大的数组局部变量这样的特殊情况除外)，但是n是10亿级别，这个时候要关注的已经不是栈空间了，而是保存数据的内存空间或cpu等资源，比如用递归方法计算Fibonacci数列，现在的个人电脑默认栈空间(M级别)，不可能栈溢出的，忙不过来的是cpu，多分的情况栈空间一般都不会过深，原因是一边调用增加深度，一边返回减少深度，用完全平衡二叉树为例，画一个图看一下调用过程就一目了然。
下面就栈空间的使用，尾递归，递归循环的转换等问题详细分析。
除非是特殊的情况，编译器能优化成不使用栈空间，否则递归是需要栈空间的，这和任何一个函数调用都是一样的，对于解决实际问题的函数，一般没有不需要栈空间的，在函数调用的时候，需要保存cpu寄存器到栈空间（用于恢复函数的执行），局部变量也有可能会导致栈空间的使用，每一个函数执行的时候局部变量都会占用一次栈空间，每一次函数调用也会触发一次栈空间的使用，这就是每一次递归调用的栈空间代价，函数调用总是有调用就有返回的，最大代价就是最大递归层数，尾递归是一种特殊情况，考虑下面的函数。
int f(int n) { if(n <= 0) return n; // body; return f(n-1); }
return f(n-1);是函数f的最后一个语句。f(n-1)的返回值就是f(n)的返回值，也就是说对于当前函数f(n)已经没有必要保存现场了，它的栈空间不需要恢复了，f(n-1)返回到f(n)，f(n)再向上返回，那为什么要留个中介呢，为什么不直接向上返回呢，所以栈空间中保存的返回地址等不动，进入f(n)时保存的寄存器(callee-saved registers)不动，也就是f(n)的上层现场不动，他们直接继承给f(n-1)，f(n-1)不再
保存它的返回地址(f(n)的最后)，也不再保存使用的寄存器(f(n)已经不需要恢复了)，f(n)的局部变量使用的栈空间直接被f(n-1)的给覆盖掉，同样的逻辑再向上递推，会发现，每一层函数调用引起的栈空间占用都相当于没有了，实际上上述代码就变成了
int f(int n) { while( n > 0 ) { //body; n--; } return n; }
这种递归叫做尾递归，即递归调用之后不需要再有额外的操作，并且递归之前没有其他递归调用，开启优化之后（gcc, O2默认开启）编译器可以将尾递归优化成循环。
再考虑下面的函数
int f(int n) { if(n <= 0) return n; // body; return n + f(n-1); }
这种递归调用是无法 直接 变成循环的，这里用直接，是因为这种情况太简单了，编译器不会那么傻，gcc O1就会变成循环，为什么不能直接变成循环呢，因为f(n-1)之后还有其他操作（返回值+n），为了继续其他操作能够继续执行，调用f(n-1)之前需要保存现场，需要用到栈空间，每一层调用都会保存一次栈空间，这时候栈空间的占用是O(n)的，因为不是二分，三分，n的数量稍大一点就会导致栈溢出。当然这里实在是太简单了！换个复杂的，编译器就不会优化了（只是写本文的时候用的gcc，不排除以后编译器越来越智能的可能）。
unsigned long fib(int n) { if(n < 2) return 1; return fib(n-1) + fib(n-2); }
fib(3) 调用 fib(2)和fib(1)，假定编译器生成的指令是先调用fib(2)，那么就要在栈空间中保存现场，以便fib(2)返回的时候能够继续执行fib(1)和一个加法操作，fib(2)调用fib(1)和fib(0)，还是假定先调用左边的，调用fib(1)的时候需要保存现场，然后返回1, 恢复现场，保存现场，调用fib(0)，然后恢复现场，加法运算，然后再返回上层，即fib(2)返回，恢复现场，fib(2)下面的所有调用占用的栈空间都已释放了(递减栈栈顶寄存器数值增加)，然后保存现场，调用fib(1)，返回1, 恢复现场，加法运算，返回，整个fib(3)就是这样完成的，可见每次调用+左边的分支的时候，递归层数会增加一层，每次调用+右面的分支的时候，左面增加的层数都已经恢复，这是一个动态增减的过程，递归层数是有限的。这种Fibonacci数列算法慢的根源在于重复计算。不重复计算的方法如下：
unsigned long fib2(int n, unsigned long left, unsigned long right) { if( n < 2 ) return right; return fib2(n - 1, right, left+right); }
这里是一个尾递归，相当于循环, 当然如果不优化，栈空间占用是O(n)，n足够大是会溢出的。
可见，循环和尾递归是直接互相转换的，循环变量相当于函数中的参数，循环退出条件相当于函数退出的条件，循环变量的增减相当于参数传递时的增减计算，循环体相当于函数体，所以像scheme这样的编程语言没有循环但是并不影响表达能力。
Fibonacci数列循环的算法是从数列的左边开始，不符合直观定义，需要知道原理才能想到，直观的定义是从右到左，然而左边又没有准备好，所以需要借用栈。
考虑一个更明显的例子，单向非循环链表的正向遍历和逆向遍历，前者是尾递归(循环)，后者非尾递归(使用循环需要借助栈)，正向遍历不需要额外的栈空间，但是如何实现逆向遍历呢？首先要拿到最后一个节点，但是访问完最后一个节点了，到哪里去找上一个节点呢，单向链表并没有prev指针，很明显，需要在内存中保存，由于访问的顺序是后进先出，用的应该是栈这种模型，而函数调用本来就是栈的模型的，所以如果使用函数调用的方式是很自然的，很符合人的思维逻辑的，用递归的方式都不用考虑栈的问题，因为这是一种很自然的符合人的逻辑的思考模型，代码如下：
struct list{ int c; struct list *next; }; #define print_list(list) (void)list void visit(const struct list *cur) { if(cur == NULL) return; print_list(cur); visit(cur->next); } void visit_reverse(const struct list *cur) { if(cur == NULL) return; // 访问后面的，怎么访问的不用管，会有人保证它的逆序 visit_reverse(cur->next); // 后面的全都访问完了，访问当前的 print_list(cur); } #define list_append(tail_p, cur) ((*tail_p)->next = cur, (*tail_p) = cur) struct list * _list_reverse(struct list *cur, struct list **tail_after_reverse) { // 最后一个 if(cur->next == NULL) { // 记录末尾，方便list_append *tail_after_reverse = cur; return cur; } struct list *head = _list_reverse(cur->next, tail_after_reverse); list_append(tail_after_reverse, cur); return head; } // 逆序单向链表 struct list * list_reverse(struct list *cur) { struct list *tail_after_reverse; if(cur == NULL) return cur; struct list *head = _list_reverse(cur, &tail_after_reverse); list_append(&tail_after_reverse, NULL); return head; }
尾递归和循环可以互相转换，这是很明显的，那么非尾递归如何和循环互相转换呢，理论上是一定可以完成的，因为对于cpu来讲递归就是用栈来实现的，下面以二叉树的先序，中序，后序的遍历方式来举例说明，不过能够实现不代表应该这样做，代码的可读性和见解性非常重要，并且转变成循环也未必就能感受到性能的变化。
#include <assert.h> #include <stdio.h> struct tree{ int n; struct tree *left; struct tree *right; }; static const void *stack[128]; static char stack_flag[128]; static int stack_i; #define visit(t) printf("%d\t", t->n) #define push(x) do{if(x) stack[stack_i++] = x;}while(0) #define pop() (stack_i == 0 ? NULL : stack[--stack_i]) #define push2(x, flag) do{if(x) {stack[stack_i] = x; stack_flag[stack_i++] = flag;}}while(0) #define pop2(flag) (stack_i == 0 ? NULL : ((flag=stack_flag[--stack_i]), (stack_flag[stack_i] = 0), stack[stack_i])) // 二叉树的先序遍历 // // 递归版本 void preorder(const struct tree *t){ if(t == NULL) return; visit(t); preorder(t->left); preorder(t->right); } // 循环版本 // 如何变成循环呢，方法就是递归怎么来，我们就怎么来， // 1. 调用visit，但是调用之后要恢复两个函数调用，为了恢复现场，需要在栈空间中保存后续要做的事，我们这里显然不需要保存cpu寄存器等，只需要保存t->left和t->right就可以了，由于是先调用t->left，后调用t->right，所以入栈就要反过来。 //push(t->right); //push(t->left); //能不能直接push(t)呢，答案是不能，除非标记t已经访问过了，否则就循环访问t了，但是标记t访问过了还是要把t->right和t->left入栈，不如就直接来，更直接。 // 2. t访问完了，递归程序就恢复现场，返回到visit的下一个地址执行，恢复现场就对应我们的出栈，继续执行同样的preorder逻辑就相当于我们重复一次循环， // 3. 递归程序继续这个过程，直到函数栈上的最底层，也就是最后一个函数调用返回，对应我们的继续这个过程，直到栈里面没有数据了为止。 // 代码如下 void preorder_loop0(const struct tree *in) { const struct tree *t = in; if(t == NULL) return; do{ visit(t); push(t->right); push(t->left); }while((t = pop()) != NULL); } //这个程序是最原始的贴近递归的版本，还可以继续优化，visit(t)之后pop出来的一定是t->left，那么下次一定是visit(t->left)，往下递推，每一次都是visit(t->left)，也就是说按照一直向左的方向遍历就可以了，需要入栈的只是右子树，但是右子树谁先谁后呢，从递归程序可以看出，所有的左子树成员都在右子树的前面遍历，也就是说最接近树根的大叉是优先级最低的，远离树根的在左子树上的右子树更优先，也就是说，入栈的顺序和访问的顺序相同，即 // void preorder_loop1(const struct tree *in) { const struct tree *t = in; if(t == NULL) return; do{ while(t) { visit(t); push(t->right); t = t->left; } }while((t = pop()) != NULL); } // 将上面两种版本对比，想象一下preorder_loop0的执行过程，也可以直接优化为preorder_loop1 //中序遍历 // 递归版本 void inorder(const struct tree *t){ if(t == NULL) return; inorder(t->left); visit(t); inorder(t->right); } // 第一步还是按照和递归一一对应的方式来转换成循环，这个地方有点复杂，因为第一个函数不是visit，本身就是个递归的，这时候的处理方式不唯一，可以直接把递归版本函数中最上面的那个inorder展开，也可以按照通用的循环中的逻辑来处理那个inorder，前者直接就是优化之后的了。另外由于inorder和visit是两种操作，为了区分是哪一种操作，还需要在入栈的时候加标记等。 void inorder_loop0(const struct tree *in) { int is_visit = 0; const struct tree *t = in; if(t == NULL) return; do{ if(is_visit) visit(t); else { push2(t->right, 0); push2(t, 1); push2(t->left, 0); } }while((t = pop2(is_visit)) != NULL); } // 简化push(t->left); 同preorder的方法 void inorder_loop1(const struct tree *in) { int is_visit = 0; const struct tree *t = in; if(t == NULL) return; do{ if(is_visit) visit(t); else { while(t) { push2(t->right, 0); push2(t, 1); t = t->left; } } }while((t = pop2(is_visit)) != NULL); } // 继续优化，每次pop出来的一定是先visit的，然后接着就是它的right，那么两者可以合成一个整体，这样也不用标记是否是is_visit了 void inorder_loop2(const struct tree *in) { const struct tree *t = in; if(t == NULL) return; while(t) { push(t); t = t->left; } while((t = pop()) != NULL) { visit(t); // pop -> t if(t->right) // pop -> t->right { t = t->right; while(t) { push(t); t = t->left; } } } } // 后续遍历 // 递归版本 void postorder(const struct tree *t){ if(t == NULL) return; postorder(t->left); postorder(t->right); visit(t); } // 和中序遍历相同的方式，唯一一个区别就是 visit(t) 和postorder(t->right)的顺序换了一下，也就是入栈的顺序换了一下。代码如下： void postorder_loop0(const struct tree *in) { int is_visit = 0; const struct tree *t = in; if(t == NULL) return; do{ if(is_visit) visit(t); else { push2(t, 1); push2(t->right, 0); push2(t->left, 0); } }while((t = pop2(is_visit)) != NULL); } // 前面已经用过这种思路，去掉push t->left(附带的pop也一起去掉了) void postorder_loop1(const struct tree *in) { int is_visit = 0; const struct tree *t = in; if(t == NULL) return; do{ if(is_visit) visit(t); else { while(t) { push2(t, 1); push2(t->right, 0); t = t->left; } } }while((t = pop2(is_visit)) != NULL); } // t->right 先出栈，处理完整棵树才能继续处理t(即visit(t))，所以t和t->right不能当成一个整体来优化 // 但仍然可以继续优化，t->right的处理过程是先push 它自己，也就是说visit(t)的时候上一次pop一定是 // t->right，并且pop -> t->right 然后pop -> t 的时候一定是访问t的时候，这是后序遍历的定义的必然 // 即 t->right == NULL 或last_pop/visit == t->right就是visit(t)的时刻，这样可以去掉is_visit的标记 // 使用更简单的push 和 pop void postorder_loop2(const struct tree *in) { const struct tree *t = in, *last_visit = NULL; if(t == NULL) return; while(t) { push(t); push(t->right); t = t->left; } while((t = pop()) != NULL) { if(t->right == NULL || last_visit == t->right) { visit(t); last_visit = t; } else { while(t) { push(t); push(t->right); t = t->left; } } } } int main(int argc, char *argv[]) { /* * * 4 * / \ * 2 6 * / \ / \ * 1 3 5 8 * / \ * 7 9 * * */ struct tree t[9] = { {1, NULL,NULL}, {2, &t[0],&t[2]}, {3, NULL,NULL}, {4, &t[1],&t[5]}, {5, NULL,NULL}, {6, &t[4],&t[7]}, {7, NULL,NULL}, {8, &t[6],&t[8]}, {9, NULL,NULL}, }; preorder(&t[3]); puts(""); assert(stack_i == 0); preorder_loop0(&t[3]); assert(stack_i == 0); puts(""); preorder_loop1(&t[3]); assert(stack_i == 0); puts(""); inorder(&t[3]); assert(stack_i == 0); puts(""); inorder_loop0(&t[3]); assert(stack_i == 0); puts(""); inorder_loop1(&t[3]); assert(stack_i == 0); puts(""); inorder_loop2(&t[3]); puts(""); postorder(&t[3]); puts(""); assert(stack_i == 0); postorder_loop0(&t[3]); assert(stack_i == 0); puts(""); postorder_loop1(&t[3]); assert(stack_i == 0); puts(""); postorder_loop2(&t[3]); assert(stack_i == 0); return 0; }
尾递归和非尾递归是否能转换呢，对于Fibonacci数列这样的特殊情况当然可以，但有些问题就是递归模型，比如快速排序，所以是无法直接转换的，如果非要转换的话，也是可以的，借助额外实现的栈，因为循环和尾递归是等价的，循环加额外的栈能实现的，尾递归加额外的栈也能实现，但是这样做是否有意义呢，人工精心优化的循环/尾递归程序和非尾递归相比，有时候也许能获得少量性能提升，但是代码的可读性却很差，而非尾递归程序却是非常直观。
补充一点，看编译器是否进行了尾递归优化，可以通过gdb或objdump看汇编，看尾递归发生的时候后面是否有其他操作，或者是否还有递归的调用，gcc O2一定会优化的， 如果通过试验测试，建议数字要足够大，因为优化之后的程序可能占用栈空间很小，而进程的栈空间可能又很大，所以没有进行尾递归优化依然可能不会栈溢出。
总之，递归是一种非常好的模型，栈空间一般可预测，尾递归因为利用函数实现，局部变量隔离，也会增加安全性，但是记得开优化，尽量不用栈和循环替代递归，增加代码可读性。
