函数调用自己的行为就是递归,递归必须要有终止条件,不然它会无限递归。
此程序的factorial函数参数从大到小地一级一级地调用自己,直到参数为1,然后函数就开始返回一级一级的从小到大地累乘,然后就计算出number的阶乘了。
#include<stdio.h>
#include<stdlib.h>
int factorial(int num);
int main(void)
{
int number=0;
int result=0;
printf("Calculating factorial: ");
scanf("%d",&number);
result=factorial(number);
printf("The result is %d\n",result);
system("pause");
return 0;
}
int factorial(int num)
{
if(num == 1)
return 1;
else
return num*factorial(num-1);
}
以下是《C Prinmer Plus》对于递归的描述:
我个人认为递归就是把你要干的事情抽象一个成可以有限步数解决的函数,然后某一步解决不了就再调用这个函数,直到可以解决(结束递归的条件)这个问题就返回。
下面再看一个具体的例子来了解递归。
汉诺塔由法国数学家爱德华·卢卡斯创造,他曾经编写了一个印度的古老传说:
在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。
有A、B、C三根针,A上从小到大放着n层盘子,要从A上所有的盘子移动到C盘上。
条件是一次只能移动一个盘子,无论什么时候小盘子必须在大盘子上面。
汉诺塔问题求的是把盘子从A移到C总共的移动次数是多少。
这是我之前追踪四层汉诺塔运行步骤画的笔记
事实证明,没多大帮助。
要想理解递归必须要放弃理解递归,放弃跟踪全程步骤。
解决问题是计算机的事,你只要明确要把每一步怎么传给计算机,递归两层之间怎么交接,以及递归结束的条件就可以。
要完成四层汉诺塔,需要先把第四层盘子从A柱放到C柱,而要把第四层盘子放到C柱,就要把上面三层的盘子放到B柱:
那么要把这三层盘子移到B柱,那么就要先把第三层盘子移到B柱。
要把第三层盘子移到B柱,就要把第二层盘子移到C柱子。
要把第二层盘子移到C柱,就要把第一层盘子移到B柱子。
移动一层汉诺塔到另一个柱不简单吗?
这样子把问题解决了,第四层盘子就可以移动到C柱上了。
然后把剩下的三层汉诺塔也按照上面的思想,就可以移动到C柱上了。
把大象装进冰箱需要多少步
把汉诺塔放到C柱需要多少步
抽象一下就是:
void move(int pile, char src, char tmp, char dst);
src就是源起点,tmp就是暂存区,dst就是终点
最外层的move函数完成的是把pile层汉诺塔从src经过tmp移动到dst
在move函数里面调用move函数来解决之后的问题:
move(pile - 1, src, dst, tmp);
这层move完成的是把pile-1层汉诺塔从src经过dst移动到tmp
move(1, src, tmp, dst);
这层move完成的是把最底层汉诺塔盘子从src直接移动到dst
move(pile - 1, tmp, src, dst);
这层move完成的是把pile-1层汉诺塔从tmp经过src移动到dst
每一层move函数都有他自己的起点、暂存区和终点,我们只需要把上一层的起点、暂存区和终点传过去就行了。
以下是完整代码:
#include<stdio.h>
#include<stdlib.h>
#define MAX_LEVEL 30 //设置最大层数
int steps = 0;//steps保存盘子移动次数
void move(int pile, char src, char tmp, char dst);
int main(void)
{
int levels = 0;
printf("输入汉诺塔层数(1~%d):", MAX_LEVEL);
scanf("%d", &levels);
if (levels > 0 && levels < 30)//判断是否符合层数范围
{
move(levels, 'A', 'B', 'C');
printf("共移动了%d次。\n", steps);
system("pause");
return 0;
}
printf("输入范围错误\n");
system("pause");
return 1;
}
void move(int pile, char src, char tmp, char dst)
{
if (pile == 1)//pile=1问题就好解决了
{
printf("%c --> %c\n", src, dst);
steps++;
return;
}
move(pile - 1, src, dst, tmp);
move(1, src, tmp, dst);
move(pile - 1, tmp, src, dst);
}
运行结果如下:
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/weixin_49125123/article/details/112795423
内容来源于网络,如有侵权,请联系作者删除!