递归调用即函数自身调用自身,我们把这种函数称为递归函数。
递归函数一定要有结束条件,否则会死循环。
递归调用核心是:
- 找递归公式
- 编写递归结束条件
在解决一些问题时,使用递归能降低编程的难度。
例如上楼问题:有n个台阶,一次只能上1个台阶或2个台阶,请问走到第n个台阶有几种走法?
- 找递归公式:只能从第 n-1 个台阶迈一步上第 n 个台阶 或者 从第 n-2 个台阶迈两步上第 n 个台阶。故走到第 n 个台阶走法总和为“走到第 n-1 个台阶走法总和”加上“走到第 n-2 个台阶走法总和”,即 step(n) = step(n-1) + step(n-2)
- 递归结束条件:当只有1个台阶时,1种走法;当有两个台阶时,两种走法。
#include <stdio.h>
int step(int n) {
if (1==n || 2==n) {
return n;
}
return step(n-1) + step(n-2);
}
int main() {
int n;
scanf("%d",&n); //输入台阶数
printf("%d\n", step(n));
return 0;
}