递归 迭代 循环（漫谈递归迭代循环）

好几天没有更新了，没有偷懒。随着源码的阅读，学习到了字典和集合的底层实现。字典这种数据结构的搜索效率很高，底层结构采用了效率优于红黑树的哈希表。红黑树是一种平衡二叉树，C 中的map和linux中的epoll内部都是基于红黑树实现的。学习哈希表之前，我先看了一眼红黑树，看了一眼树的前序、中序、后续遍历。然后我就看到了递归，我陷入了深思。

接下来的几篇文章，我的学习过程是这样的。递归->树->红黑树->哈希表->CPython字典底层。

刚开始看递归，前人的经验贴就给出一句大师的名言：人理解迭代，神理解递归。（To Iterate is Human, to Recurse, Divine.）我在纠结，我还要不要学习递归，我就是一个平凡的人呀。那就站在平凡人的角度，试着理解一下递归吧。

汉诺塔问题只能使用递归方法解决

维基百科上说，递归是一个过程，以一种自相似的方式重复自己。在计算机中是指在函数的定义中使用函数自身的方法。“递归”这个词是翻译过来的，recursion->re(重复) curs(发生)，看起来是重复发生的意思。重复发生的话，能想到的词就多了，迭代，循环，也有重复发生的意思。

递归:以自相似的方法重复自己，A调用A；递归是一个树结构，这种重复包括递推和回归两个过程，当递推到达底部就开始回归，这个过程和树的深度优先遍历有点像。

迭代：重复反馈过程的活动，每一次迭代的结果会作为下一次迭代的初始值，A调用B；递归是一个环结构，从初始状态开始，每次迭代都遍历这个环，并更新状态，多次迭代直到结束状态。

图示递归

计算n的阶乘，先看一下递归的实现代码

递归三要素必须要有：

1、明确递归终止条件

2、给出递归终止时的处理办法

3、提取重复的逻辑，缩小问题规模

int func（int n） { if(n == 1)////明确递归终止条件 return 1;//递归终止时的处理办法 else { return n*func(n - 1);//提取重复逻辑，缩小问题规模 } } //代码运行时，func(n)->func(n-1)->.......func(3)->func(2)->func(1)，不断地调用函数自身。

图示迭代

计算n的阶乘，再看一下迭代的实现代码：

int func(int n) { int result = 1;//有初始值的初始变量 for(int i = 2; i < n; i )//一个结束条件 { result *= i;//变量值如何更新的规则 } return result; } //与递归相比，迭代没有调用自己本身。

迭代三要素必须要有：

1、一个有初始值的初始变量

2、一个说明变量值如何更新的规则

3、一个结束条件

从这里可以看出，迭代和循环是很像的，我们看一下如何用循环计算n的阶乘：

int func(int n) { int result = n;//有初始值的初始变量 while(n > 1)//一个结束条件 { n--; result = result * n//一个说明变量值如何更新的规则 } return result; } //与迭代相比，循环可以是不变的重复，和可变的重复。

迭代是一种变化的循环，轮流代替；循环是不变的重复，和可变的重复。

从理论上讲，所有递归函数都可以转换为迭代函数，反之亦然。但从算法结构来说，递归声明的结构并不是总能转换为迭代结构，原因可能是结构的引申本身属于递归的概念，用迭代的方法在涉及结构初期根本无法实现。这也是为甚在结构设计时，通常采用递归的方式而不是采用迭代的方式。尤其是树、链表、图、网络等问题，使用迭代从描述和实现上都变得很不现实。

递归其实是为了方便程序员难为了CPU。递归是用栈机制实现的，每深入一层，都要占用一块栈数据区域。递归程序改用循环实现的话，一般要自己维护一个栈，以便状态回溯。递归程序就是为了利用函数自身在系统上的自动变量记录状态，以便回溯。递归的优点是易理解，容易编程；缺点是对于嵌套层数较深的一些算法，空间上内存会力不从心，大量的函数调用，也会有许多额外的时间开销。循环的缺点是不容易理解，编写复杂问题时困难；优点是效率比较高，运行时间只因循环次数增加而增加，空间上没有额外的开销。

1、问题的解法是递归的，汉诺塔问题只能使用递归方法解决。

2、问题的定义是按照递归定义的，像阶乘、斐波那契额函数。

3、数据结构是递归的，如链表和树的操作，包括树的遍历（前序，中序，后序）

树本身就是使用递归定义的，因此使用递归的方法实现遍历，代码简洁且容易理解，但是开销比较大；使用循环方法实现遍历，要用栈来模拟实现。

使用递归方法先序遍历二叉树，先序是指先根序， 根节点->左孩子->右孩子

//先序遍历二叉树 根节点-左孩子-右孩子 void pre_traverse(BTree pTree) { if(pTree)//明确递归终止条件 { printf("%c",pTree->data);//递归终止时的处理办法 if(pTree->pLchild) pre_traverse(pTree->pLchild);//提取重复逻辑，缩小问题规模 if(pTree->pRchild) pre_traverse(pTree->pRchild);//提取重复逻辑，缩小问题规模 } }

使用循环方法先序遍历二叉树，先序是指先根序， 根节点->左孩子->右孩子

void pre_traverse(BTree pTree) { PSTACK stack = create_stack();//创建一个空栈 BTree node_pop; //用来保存出栈节点 BTree pCur = pTree; //定义用来指向当前访问的节点的指针 //直到当前节点pCur为NULL且栈为空时，循环 结束 while(pCur || !is_empty(stack)) { //从根节点开始，输出当前节点，并将其入栈 //同时置其左孩子为当前节点，直至其没有左孩子，及当前节点为NULL printf("%c",pCur->data); push_stack(stack,pCur); pCur = pCur->pLchild; //如果当前节点pCur为NULL且栈不空，则将栈顶节点出栈 //同时置其右孩子为当前节点，循环判断，直至pCur不为空 while(！pCur && !is_empty(stack)) { PCur = getTop(stack); pop_stack(stack,&node_pop); pCur = pCur->pRchild; } } }