概念
什么是递归？一个方法在方法内部直接或间接调用自身方法。
应用场景
下面3中情况，我们通常使用递归解决问题
1.定义是递归的
例如斐波拉契数列
long Fib(Long n){
if(n == 1 || n == 2) return 1;
else return Fib(n-1)+Fib(n-2);
}
对于类似这种复杂问题，若能够分解成几个简单揭发相同或类似的子问题来求解，便成为递归求解
采取分治法进行递归求解的问题需要满足以下三个条件：
- 能讲一个问题转换成一个小问题。而新问题和原问题揭发相同或雷同。不同的仅仅是处理的对象，并且这些处理更小且变化有规律的
- 可以通过上述转换而使得问题简化
- 必须有一个明确的递归出口，或成为二递归边界
2.数据结构是递归的
其数据结构本身具有递归的特性
例如，对于链表，其结点LNode的定义由数据域data和指针域next组成，而指针域next是一种指向LNode类型的指针，即LNode的定义中又用到了其自身，所以链表是一种递归的数据结构
void TraverseList(LinkList p){
//
if(p == NULL) return; else{
// printf("%d",p->data); //p TraverseList(p->next);
}
10 11 }
3、问题的解法是递归的
有一类问题，虽然问题本身并没有明显的递归结构，但是采用递归求解比迭代求解更简单，如Hanoi塔问题，八皇后问题，迷宫问题
递归过程与递归工作栈
一个递归函数，在函数的执行过程中，需要多次进行自我调用。递归函数是如何执行的？
在高级语言的程序中，调用函数和被调用的函数之间的链接与信息交换都是通过栈来进行的
通常，当在一个函数的运行期间调用另一个函数时，在运行被调用函数之前，系统需要先完成3件事情：
- 将所有的实参、返回地址等信息传递给被调用函数保存
- 为被调用函数的局部变量分配存储空间
- 将控制转移到被调用函数入口
而从被调用函数返回到调用函数之前，系统同样需要完成3件事 - 不存被调用函数的计算结果
- 释放被调用函数的数据区
- 依照被调用函数保存的返回地址将控制器移动到调用函数
当多个函数构成嵌套调用时，按照“先调用后返回”的原则，上述函数之间的信息传递和控制转移必须通过“栈”来实现。即系统将整个程序运行时的所需要的数据空间都安排在一个栈中，每当调用一个函数时，就在他的栈顶分配一个存储区。每当整个函数退出时，就释放它的存储区。则当前运行时的函数的数据区必在栈顶
一个递归函数的运行过程类似多个函数嵌套调用，只是调用函数和被调用函数是同一个函数。因此，和每次调用相关的一个重要概念是递归函数运行的层次。假设调用该递归函数的主函数是第0层，则从主函数调用递归函数进入第一层，从第i层递归调用本函数为下一层。即第i+1层。反正退出第i层递归应返回上一层，即第i-1层。
为了保证递归函数正确执行，系统需要设立一个“递归工作栈”作为整个递归函数运行期间使用的数据存储区，每一层递归所需信息构成一个工作记录，其中包括所有的实参，所有的局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一个递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必须是递归工作栈顶的工作记录，称为活动记录
