当前位置：首页 > ds >正文

C语言中的递归1.0

ds 2025/7/13 2:57:58

一、递归函数概念引入

简单来说就是自己调用自己

递归函数满足的两个条件:

1.每次调用函数本身,必须一次又一次接近最终结果

2.必须有停止条件

二、代码展示

用递归求1到4的和代码如下

三、代码分析

首先进入main主函数入口

int sum = getsum(4);

就这个具体题目来看我们要求的是1到4的和

定义一个名为sum的变量把getsum的调用函数的值赋值给sum

这时我们进入了getsum的函数调用部分

我们会从main主函数跳出来到getsum函数里面

当n的值为1的时候即getsum(1)和为1 此时返回值是1

可以理解为我们要求的是1到4的和那么从1开始那么就是返回值是1 n值为1时即和为和为0 终止

然后逆着往回去带入数值

这一个题目进入main函数这样看首先是getsum(4)

然后跳出main函数进入了getsum函数里面

第一次 n==4 不满足n==1 所以他不会得到返回值

伪代码分析:

当n==4时 temp = getsum(3) 得到返回值temp+n=getsum(3)+4

这时得到了getsum(3) 又要调用函数getsum了

当n==3时 temp = getsum(2) 得到返回值temp+n=getsum(2)+3

这时得到了getsum(2) 又要调用函数getsum了

当n==2时 temp = getsum(1) 得到返回值temp+n=getsum(1)+2

这时得到了getsum(1) 又要调用函数getsum了

但是此时n的值是1了那么返回值就是1了那么将把n的值往回带

temp+n=getsum(3)+4

=getsum(2)+3+4

=getsum(1)+2+3+4

=1+2+3+4

=10

最后我们算出getsum函数的返回值是temp+n即是10 所以

回到main函数中int sum=10 把函数getsum的返回值给sum

最后打印出来那么sum的值就是10

总结

递归的核心就是"递"和"归"的结合

四、运行结果

五、拓展延伸

汉诺塔圆盘规则:

只能动最上面的圆盘，大圆盘不能压小圆盘，借助中间柱子把圆盘全移到目标柱

推算过程:

假设圆盘个数为n,移动次数是f(n)

当n=1时, 只需要将圆盘从A移动到C,f(n)是1

当n=2时, 只需要将圆盘从A移动到C,f(n)是3,只能动最上面的圆盘，大圆盘不能压小圆盘，借助中间柱子把圆盘全移到目标柱

由于我们已经知道可以将圆盘从 A 移动到 C，且移动次数 f(2) 是 3 现在，我们在这个基础上进行续写，推导 n≥3 时的情况。

当 n=3 时，可以按照如下步骤进行：

将最上面的圆盘（即最小的圆盘）从 A 移动到 C。这一步需要1次移动。

将剩下的两个圆盘（看作一个整体，视为一个较大的圆盘）从 A 移动到 B。这一步实际上是 f(2)=3 次移动（即将两个圆盘从 A 通过 C 移动到 B）。

最后，将最上面的那个圆盘（之前从 A 移动到 C 的那个）从 C 移动回 B（这是为了空出 C 柱以便接收接下来的圆盘），然后将剩下的两个圆盘（之前在 B 柱上的那两个）从 B 移动到 C。

这一步又需要 f(2)=3 次移动，但加上之前从 C 移动回 B 的那一次，总共是 3+1=4 次中的最后1次与 f(2) 的3次合并计算，所以整体上看作是再进行了 f(2) 次移动后加上最初从 A 到 C 的1次，共 1+3+3=7 次中的关键步骤合并，

简化为理解上的 f(3)=f(2)+1+f(2)=2f(2)+1 的递推形式，即实际执行是7步但逻辑上表达为基于 f(2) 的递推，这里为了符合递推式表述我们按逻辑上的 2f(2)+1 来理解，即 f(3)=2×3+1=7，但实际操作是1到C，2个作为整体3步从A经C到B，再将1从C移到B（此步为逻辑上的合并步骤，实际是执行中的一步），然后整体2个从B到C的3步，共7步。

这个汉诺塔的推导过程理解不了没有关系可以先把规律记住如下:

总结:

当n=1时,f(1)=1

当n=2时, ,f(2)=3

当n=3时, ,f(3)=7

以此类推……

通过观察和归纳，我们可以发现对于 n≥2 的情况，移动次数 f(n) 可以表示为：

总结的规律为:

f(n)=2f(n−1)+1

反过来带进去验证一下

当n=2时, ,f(2)=2f(1)+1=2×1+1=3

当n=3时, ,f(3)=2f(2)+1=2×3+1=7