©一颗斯特拉
【注】
DEF：定义
知识点提炼
DEF[递归函数]：一个函数在它的函数体内调用它自身称为递归调用。这种函数称为递归函数。
为防止递归调用无终止进行，必须在函数内有终止递归函数调用的手段。常用的方法是加条件判断，满足某种条件后就不再做递归调用，然后逐层返回。
实例1
题目：用递归算法计算n!。
程序源代码：
#include<stdio.h>
long factorial(int n) {
if(n<0) {
printf("输入错误!请输入非负整数。");
return -1;
}
else if(n<=1)
return 1;
else
return factorial(n-1)*n;
}
int main(){
int n;
printf("请输入n:");
scanf("%d",&n);
if(factorial(n)>=1)
printf("%d!= %ld",n,factorial(n));
return 0;
}
【运行结果】
请输入n:10
10!= 3628800
题目总结：
程序中给出的函数factorial是一个递归函数。主函数调用factorial后进入函数factorial执行，如果n<0,n=0或者n=1时都将结束函数的执行，否则就递归调用自身。由于每次递归调用的实参为n-1，即把n-1的值赋予形参n，最后当n-1的值为1时再做递归调用，形参n的值也为1，将使递归终止。然后可逐层返回。
实例1求阶乘可以用递归法也可以用递推法，递推法更简单和易懂。但有些问题只能用递归法。如下面的Hanoi塔问题。
实例2
题目：一块板上有三根针，A,B,C。A针上套有64个大小不等的圆盘，大的在下，小的在上。要把这n个圆盘从A移到C针上，每次只能移动一个圆盘，移动可以借助B针。但在任何时候，任何针上的圆盘都必须保持大盘在下，小盘在上。求移动的步骤。
程序分析
这道题的关键是任何时候都必须保持大盘在下，小盘在上，且每次只能移动一个圆盘。
如果n=1，则直接将A上的取下到C。
如果n=2，则分两三步走：
先将A上面的1个（n-1）取下放到B针，再将A下面的1个放到C针，最后将B针上的取下放到C针。
如果n=3，也分两三步走：
第一步，将A针上的2个（n-1）在C的帮助下放到B针上。
第二步，将A针最后的1个放到C针上。
第三步，将B针上的2个（n-1）在A的帮助下放到C针上。
第一步和第三步是类似的过程，可以用一个函数。
这样一归纳，当时，总共就是三大步：
第一步，将A针上的n-1个在C的帮助下放到B针上。
第二步，将A针最后的1个放到C针上。（这个是递归出口）
第三步，将B针上的n-1个在A的帮助下放到C针上。
程序源代码：
#include<stdio.h>
void move(int n, char x,char y, char z)//move函数的功能是把x上的n个圆盘移到z上
{
if(n==1)
printf("%c-->%c\n",x,z);
else
{
move(n-1,x,z,y);
printf("%c-->%c\n",x,z);
move(n-1,y,x,z);
}
}
int main()
{
int h=4;
move(h,'a','b','c');
}
【运行结果】
a-->b
a-->c
b-->c
a-->b
c-->a
c-->b
a-->b
a-->c
b-->c
b-->a
c-->a
b-->c
a-->b
a-->c
b-->c
题目总结：
暂无
——4.16更新——
看了《从一到无穷大》后知道原来汉诺塔问题起源于法国数学家爱德华·卢卡斯曾编写过的一个印度的古老传说，至今也有人相信着婆罗门一刻不停地在搬动圆盘。
