函数的递归
1.定义：递归函数是自己调用自己的函数，每次调用函数都会开辟新的内存空间，递归调用可以看成函数的嵌套调用
举例：如下图是一个递归调用的例子，main函数执行到recur()时，开始调用recur()函数，将这次调用称为recur1,recur1往下执行，于是在内存内开辟一份内存空间，从头往下执行，在recur1定义一个变量c，在键盘上输入abc回车时，c被赋值为a,因为a不等于’\n’，于是会再次调用recur函数，于是在内存空间里面再开辟出新的内存空间，将recur放进去再次执行，将这次执行称为recur2,此时又会定义一个新的变量c,将读取的b赋值给c,继续向下执行，又执行到recur,再内存中再次开辟一份内存空间，从头往下执行，这是会读取c,因为c不等于换行符，有调用recur,再从内存中开辟一份内存空间，读取c,这是c为换行符，所以执行输出换行符，然后返回到recur3中调用的位置继续执行，于是打印出字母c,然后返回recur2中调用的位置打印字母b,最终输出为cba.。当一个函数调用了另一个函数，在被调用函数返回以后，调用它的函数还会继续往下执行.
2.递归的作用：
- 用递归来完成递推
- 模拟连续发生的动作
2.1 用递归来完成递推（切饼、斐波那契数列）
这类问题的方法：
切饼：
第0刀时饼是一块
第1刀时饼多了一块
第2刀时饼多了两块
...........
分析：一.是找第n次做与第n-1次做之间的关系，该题的关系是q(n) = q(n-1) + n
二.获取当n处于边界条件下，函数的返回结果，该题当n=0时，q(0)=1
知道 了这两个条件，就可以写出递推关系式了。
代码实现：
#include<stdio.h>
int fun(int n)
{
if(n==0)
return 1; //第一次的返回结果
return (n+fun(n-1)); //第n次做与第n-1次做之间的关系
}
int main()
{
int n,i,sum;
scanf("%d",&n); //输入切的刀数
sum = fun(n);
printf("%d ",sum); //输出得到的饼数
return 0;
}
求解斐波那契数列的n个数字是多少？
第一个数字是1
第二个数字是1
第三个数字是2
.........
分析：直接看第n个数，找第n个数和第n-1之间的关系，fab(n)=fab(n-1)+fab(n-2),接着找边界条件，fab(1)=1,fab(2)=1
代码实现：
#include<stdio.h> int fun(int n) { if(n==1) return 1; if(n==2) return 1; if(n>=3) return (fun(n-1)+fun(n-2)); } int main() { int n,i; scanf("%d",&n); i = fun(n); printf("第n个数字是%d",i); return 0; }
2.2用递归来模拟连续发生动作（十进制二进制数转换，汉诺塔问题）
方法：首先要搞清楚连续发生的动作是什么
其次搞清楚不同动作之间的关系
最后搞清楚边界条件是什么
十进制二进制数转换
算法步骤：
（1）将数x除以2
（2）记录所得的余数r(必是0或者1)
（3）用的到的商作为新的被除数x
（4）重复步骤1到3，直到x为0
（5）倒序输出每次出发得到的余数
实例：
分析：反复执行除以2的步骤，直到余数为1停止。
代码实现：
void to_binary(long n) { int r; r = n%2; if(n>0) to_binary(n/2); printf("%d ",r); } int main() { int n; scanf("%d ",&n); to_binary(n); }说明：
1）递归函数中，位于递归调用前的语句和各级被调函数具有相同的执行顺序，位于递归调用后的语句的执行顺序和各个被调函数的顺序相反。
2）计算出的第一个数值r反而在最后一个输出。
汉诺塔问题：
规则：（1）每次只能移动一个盘子
（2）出现在柱子上的圆盘，保证大的在下面
分析：下图是将一个盘子，两个盘子，三个盘子移动的图。
当A只有一个盘子的时候，直接将A中的盘子移动到C中。
当A有两个盘子的时候，先将A中第一个盘子移动到B，将A中第二个盘子移动到C，最后将B中的盘子移动到C
当A有三个盘子的时候，先将A中第一和第二个盘子移动到B（移动方法第二幅图已经给出），在将第三个盘子移动到C，最后将B中的盘子移动到C（移动方法第二幅图已经给出）
对应的代码表示：
说明：move(n,1,2,3)将n个盘子从1经过2移动到3。
同理移动四个盘子的情况就会被简化为移动=三个盘子的情况，当我们有n个盘子的时候就被演化为有n-1个盘子的情况，如下图
要将n个盘子从A经过B移动到C，需要先将n-1个盘子从A经过C移动到B，再将最后一个盘子（绿色）从A移动到C，最后再将n-1个盘子从B经过A移动到C。
代码实现：
#include <stdio.h>
//递归实现汉诺塔的移动
void move(int m,char x,char y,char z)
{
if(m==1)
{
printf("将盘子从%c移动到%c",x,z);
}
else
{
move(m-1,x,z,y);
printf("将盘子从%c移动到%c",x,z);
move(m-1,y,x,z);
}
}
int main()
{
int n;
char x,z;
printf("要移动盘子数");
scanf("%d",&n);
move(n,'A','B','C');
return 0;
}