递归：函数自己调用自己，函数的这种嵌套作用；一般会有个通项公式（山里有座庙一直持续下去（盗梦空间），不知道什么时候结束，回到现在）
1.写数据算法时，可以不用考虑内部是怎么计算的，只管实现自己调用的思想；
2.相当于把循环for递推换成了选择if递归，容易理解，但效率低了点。
例1：求一个数的阶乘
/*
头文件
接口的定义
函数的功能：
函数的输入参数
函数的返回值
int getFactorial(int n);
*/
//源程序
//递归算法完成阶乘
int getFactorial(int n)
{
int result;
if(n==0)
{
result=1;
}
else if(n==1)
{
result=1;
}
else
{
result=n*getFactorial(n-1);//这个函数就是在求阶乘 n-1项求出来
}
return result;
}
//测试客户端程序
#include<stdio.h>
//#include"MyMath.h"//把上面那个程序放入头文件的名称
int main()
{
int n;
int iFacResult;
printf("please input n:");
scanf("%d",&n);
iFacResult=getFactorial(n);
printf("%d!=%d",n,iFacResult);
}
例2：汉诺塔
#include<stdio.h>
void hanoi(int n,char A,char B,char C)//没有做计算，只是输出，无返回值，所以void
{
if(n==1)
{
printf("%c->%c\n",A,C);
}
else
{
hanoi(n-1,A,C,B);//这个函数就是移盘子
printf("%c->%c\n",A,C);
hanoi(n-1,B,A,C);
}
}
int main()
{
hanoi(3,'A','B','C');
return 0;
}
例3：斐波那契数列
#include<stdio.h>
int main()
{
int n;
printf("inout n:");
scanf("%d",&n);
printf("第%d项数据是%d",n,getFibonacci(n));//注意这里定义到的是函数
return 1;
}
int getFibonacci(int n)//计算了结果需要返回
{
int result;
if(n==1)
{
result=1;
}
else if(n==2)
{
result=1;
}
else
{
result=getFibonacci(n-1)+getFibonacci(n-2);
}
return result;
}
例4：二进制
1 本题要求实现一个函数，将正整数n转换为二进制后输出。
2 void dectobin( int n )
3 {
4 if(n == 0)
5 printf("0");
6 else if(n == 1)
7 printf("1");
8 else
9 {
10 //0 1 2 3 4 5 6 7 8 9
11 //0 1 10 11 100 101 110 111 1000 1001
12 dectobin(n/2);//利用二进制的原理,求当前数的一半那个数的二进制
13 printf("%d", n%2);//加上在连接当前这个数和2的余数
14 }
15 }
例5：递归与递推的互换
1 本题要求实现一个函数，计算下列简单交错幂级数的部分和：
2
3 f(x,n)=x−x2+x3 −x4+⋯+(−1)n−1xn
4 double fn( double x, int n )
5 {
6 int i=1,j=1;
7 double sum=0;
8 for(i=1;i<=n;i++)
9 {
10 sum=pow(x,i)*j+sum;
11 j=j*(-1);
12 }
13 return sum;
14 }
15 /* 递归
if(n==1)
16 {
17 return x;
18 }
19 else
20 {
21 return fn(x,n-1)+pow(-1.0,n-1)*pow(x,n);前n-1项加上第n项；自己回味
22 }
23 */
1 本题要求实现一个计算非负整数阶乘的简单函数，并利用该函数求 1!+2!+3!+...+n! 的值。
2 double fact( int n )
3 {
4 double i;
5 double fac=1;
6 for(i=1;i<=n;i++)
7 {
8 fac=fac*i;
9 }
10 return fac;
11 }
12 double factsum( int n )
13 {
14 double sum=0;
15 double i;
16 for(i=1;i<=n;i++)
17 {
18 sum=sum+fact(i);
19 }
20 return sum;
21 }
22 /*递归：if(n==0||n==1)
23 {
24 return 1;
25 }
26 else
27 {
28 return n*fact(n-1)求前n-1项
29 }
30 if(n==1)
31 {
32 return 1;
33 }
34 else
35 {
36 return factsum(n-1)+fact(n);很多情况下循环与阶乘可以互换
37 }
38 */