第一类、递归调用（13 道）
1.汉诺塔：请输入盘子数，输出盘子移动的操作步骤。
include <stdio.h>
void move(char from, char to) {
printf("%c to %c\n", from, to);
}
void hanoi(int n, char a, char b, char c) {
if (n == 1)
move(a, c);
else {
hanoi(n - 1, a, c, b);
move(a, c);
hanoi(n - 1, b, a, c);
}
}
void main() {
int n;
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
}
2.爬楼梯：树老师爬楼梯，他可以每次走 1 级或者 2 级，输入楼梯的级数，求不
同的走法数。
include <stdio.h>
int stair(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return stair(n - 1) + stair(n - 2);
}
void main() {
int n;
scanf("%d", &n);
printf("%d", stair(n));
}
3.爬楼梯：树老师爬楼梯，他可以每次走 1 级、2 级或者 3 级，输入楼梯的级数，
求不同的走法数。
include <stdio.h>
int stair(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
if (n == 3) return 4;
return stair(n - 1) + stair(n - 2) + stair(n - 3);
}
void main() {
int n;
scanf("%d", &n);
printf("%d", stair(n));
}
4.斐波那契数列：请输入项数，输出具体数列。
include <stdio.h>
int fibonacci(int n) {
if (n == 1 || n == 2)
return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
void main() {
int n, i;
scanf("%d", &n);
for (i = 1; i <= n; i++)
printf("%d,", fibonacci(i));
}
5.求阶乘：请输入整数 n，求 1!+2!+3!+4!+5!+6!+7!+...+n!的和。
include <stdio.h>
int factorial(int n) {
if (n == 1) return 1;
return n * factorial(n - 1);
}
void main() {
int n, i, sum = 0;
scanf("%d", &n);
for (i = 1; i <= n; i++)
sum += factorial(i);
printf("sum=%d", sum);
}
6.取球问题：在 n 个球中，任意取 m 个（不放回），求有多少种不同取法。
include <stdio.h>
int ball(int n, int m) {
if (n < m) return 0;
if (n == m) return 1;
if (m == 0) return 1;
return ball(n - 1, m - 1) + ball(n - 1, m);
}
void main() {
int n, m;
scanf("%d%d", &n, &m);
printf("%d", ball(n, m));
}
7.杨辉三角：输入要打印的层数，打印杨辉三角。
include <stdio.h>
int triangle(int m, int n) {
if (m == 0 || n == 0 || m == n)
return 1;
return triangle(m - 1, n) + triangle(m - 1, n - 1);
}
void main() {
int n, i, j;
scanf("%d", &n);
for (i = 0; i < n; i++) {
for (j = 0; j <= i; j++) {
printf("%d ", triangle(i, j));
}
printf("\n");
}
}
