什么是递归？
程序调用自身解决问题的编程技巧称为递归（百度百科）
递归不能称得上是一种算法，而是一种符合人解题逻辑的编程技巧。
比较经典的问题比如汉诺塔、斐波那契数、上楼梯问题等。
怎么理解递归
首先明确他和普通的函数调用没有什么不同，只是递归一般不是立刻可以得到结果的，要经历一连串的“挂起”、“入栈”、“出栈”的过程来解决问题。
看一个斐波那契数的例子
斐波那契数后一个数等于前面两个数的和。在这个数列中的数字，就被称为斐波那契数。如数列1、1、2、3、5、8、13.......
代码语言：javascript复制//斐波那契数递归写法
int Fib_1(int i){
if(i<=2)
return 1;
else
return Fib_1(i-1) Fib_1(i-2);
} 上面代码通过一个简单的判断结果就可以求得第N个斐波那契数，但是对于新手这段代码却是不好理解的。
根据斐波那契数的逻辑规律想一个问题解法，an= a(n-1) a(n-2);
于是就有的第5行的递归调用。我是这样理解递归的，假如我们要执行Fib_1(4)是这样的过程。
① Fib_1(4)进栈Fib_1(3) Fib_1(2)，并挂起；递归调用Fib_1(3)
② Fib_1(3)进栈Fib_1(2) Fib_1(1)，并挂起；递归调用Fib_1(2)
③ Fib_1(2)进栈，得到结果“1”，出栈。Fib_1(1)进栈，得到结果“1”。
④ 执行return Fib_1(2) Fib_1(1) = 2; Fib_1(3)执行完出栈，
⑤ ②执行过程中的Fib_1(2)进栈，执行return 1，②过程中Fib_1(2)出栈;
⑥ 得到②过程中Fib_1(2) Fib_1(1)结果，Fib_1(3)出栈。
⑦ 执行①中的Fib_1(2)进栈，执行return 1，①过程中Fib_1(2)出栈;
⑧ 得到①Fib_1(3) Fib_1(2)的结果，出栈，程序结束。
上面是斐波那契数递归解法的部分过程。递归程序有两部分组成“基准情况”和“不断推进”两个程序段，通俗点说就是“递归出口”和“不断递归深入”两个名词。也就产生了入栈、挂起、出栈的情况。（挂起只是我用来加深理解想的名词，大家随意）。另一方面一次函数的调用，栈里会存储函数调用的信息，比如返回结果的地址，形式参数具体的值，当函数达到递归出口时会根据这些信息返回结果。上面就是我对递归的理解。
用递归解决实际问题。
编写递归程序时要遵循四条法则（《数据结构与算法分析—C语言版》）
（一）基准情况：必须要有递归出口
（二）不断推进：程序的设计要一步步向基准情况推进。
（三）设计法则：假设所有递归调用都能运行。
（四）合成效益法则：设计递归时避免做重复的工作。
关于㈢设计法则，我们可以通过上面冗长的递归代码分析可以看到，对于一个复杂的递归，你不可能全面的了解每一步，这就要求我们考虑好问题，想好算法，满足算法设计的五大重要特征：有限性、确定性、可行性、输入性、输出性。才能保证递归算法的正确性。
关于㈣合成效益法则，通过书上的一个图可以更好的理解
通过上面这一个图我们可以看到F3被计算了三次，F2被计算了5次，这就违反了第四条准则“合成效益”，虽然可以得到正确的结果，逻辑上也好理解，但是当运算量达到了一定程度，就会出现出栈的情况，而且它确实不能称的上是一个好的算法。
代码语言：javascript复制//斐波那契数循环写法
int Fib_2(int i){
int k=0,fib,fib1,fib2;
for(;k<=i;k ){
if(k<=2){
fib=fib1=fib2=1;
}else{
fib2 = fib1;
fib1 = fib;
fib = fib1 fib2;
}
}
return fib;
}写到这里感觉我好像在抄书，我现在的角色应该是《数据结构与算法分析—C语言版》作者思想的接受者和传播者而不是创新者。
