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

【c语言】函数：递归（详解+做题技巧）

java 2025/6/30 16:50:07

今天学习递归算法~~：

一、递归思想：

1.1 递归函数

1.2 新手技巧

二、基础习题

2.1 n的阶乘

2.2 输出数字

2.3 池塘里生长的荷花

2.4 各种公式

三、进阶习题

3.1汉诺塔问题

3.2 跳台阶问题

四、总结

(*^▽^*)

一、递归思想：

将一个复杂的问题P0，转化为类似而更简单的问题P1，再将P1转化为类似而更简单的问题
p2，依次类推，直到推出的问题Pn足够简单，可以立即求解为止。

1.1 递归函数

如果在定义一个函数时，又直接或间接地调用了这个函数自身，就称之为递归函数。

1.2 新手技巧

a.不需要把精力放在每一层递归的细节里，所要做的就是充分相信你写的递
归，然后把精力放在出口的设计就行。

b.从创建那个递归函数的子程序开始，你就要假设他能够解決你赋予他的使命，不论你这个子程
序有没有写完。

c.可以猜想本身函数的递归只有两次，然后直接去推导这所谓两次的过程，然后直接写出代码，最后把更多的情况考虑进去看一下可不可以实现即可。

以下是具体应用：

二、基础习题

2.1 n的阶乘

输入案例：

输出案例：

5！=120

代码如下：

#include<stdio.h>
int f(int n)
{int r;if(n==1)return 1;else{r=n*f(n-1);return r;}
}
int main()
{int n;scanf("%d",&n);int y;y=f(n);printf("%d!=%d",n,y);return 0;
}

解题思路：

参考新手方法：

想象要求的是求2的阶乘，则要实现的是2*f（1），而f（1）=1；则可得出。

如果想要更透彻的理解，则可以代3进去，会发现实现的是3*f（2），而由刚才得到的f（2）=2；可得f（3）的值。

2.2 输出数字

输入案例：

输出案例：

1 2 3 4

代码如下：

#include <stdio.h>
void f(int n)
{if(n<9)printf("%d ",n);else{f(n/10);printf("%d ",n%10);}
}
int main()
{int n;scanf("%d",&n);f(n);return 0;
}

参考解题思路：

可以先用34思考：

则可分两步：1、输出34/10 2、输出34%10

接下来扩大到234代入程序检验顺序是否合适即可

2.3 池塘里生长的荷花

这个需要讲一下题目了：

输入：无

输出：

0.25

代码如下：

#include <stdio.h>
int f(int n)
{	if(n==30)return 1;else{return 2.0*f(n+1);}
}
int main()
{int m;int n=28;m=f(n);printf("%.2f",1.0/m);return 0;
}

参考解题思路：
本题目主要是想解决一下逆推问题，由本题可知递归出口的设计至关重要

从29天假设，则结果绝对是1/2，所以2*f（30）=2；

则又与上题的推导过程类似了(〃'▽'〃)

2.4 各种公式

题目：

题目说明：n是正整数，x是浮点数，输入n与x，计算f（x，n）的值

输入案例：

5 3.2

输出案例：

2.74

代码如下：

#include <stdio.h>
#include <math.h>
float f(int n,float x)
{float m;if(n==1)return 1+x;else{m=sqrt(n+f(n-1,x));}return m;
}
int main()
{int n;float x,m;scanf("%d%f",&n,&x);m=f(n,x);printf("%.2f",m);return 0;
}

参考解题思路：
观察式子：分很多层，但每一层结构相似，那同样以2为例，则sqrt（2+f（1）），f（1）=1+x；则再次倒推回去发现是一样的道理

三、进阶习题

3.1汉诺塔问题

题目描述：

给定三根柱子，记为 A,B,C ，其中 A 柱子上有 n 个盘子，从上到下编号为 0 到 n-1 ，且上面的盘子一定比下面的盘子小，输入盘子个数，求将A中的盘子全部移动到C中盘子的所有情况。

输入案例：

输出案例：

A->C
A->B
C->B
A->C
B->A
B->C
A->C

代码如下：

#include<stdio.h>
void f(int n,char A,char B,char C)
{if(n==1)printf("%c->%c\n",A,C);//把A上的最后一块移动到C去else{f(n-1,A,C,B);//把A上头的那一堆都移动到B去printf("%c->%c\n",A,C);f(n-1,B,A,C);//把B头上的那一堆都移动到C去}return;
}int main()
{int n;scanf("%d",&n);f(n,'A','B','C');return 0;
}

参考解题思路：

该递归可能会比较抽象：

但也可以从2开始想，如图所示：

3.2 跳台阶问题

题目：
假设一次可以跳一个台阶，也可以跳两个台阶。求跳n级台阶一共有几种跳法？

样例输入：

样例输出：

代码如下：

#include <stdio.h>
long f(int n)
{if(n==1)return 1;if(n==2)return 2;return f(n-1)+f(n-2);
}
int main()
{int n;scanf("%d",&n);long m;m=f(n);printf("%ld",m);return 0; 
}