漫谈递归、迭代、循环——人理解迭代，神理解递归
后续计划
好几天没有更新了，没有偷懒。随着源码的阅读，学习到了字典和集合的底层实现。字典这种数据结构的搜索效率很高，底层结构采用了效率优于红黑树的哈希表。红黑树是一种平衡二叉树，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;
}
}
}