實例講解｜徹底弄懂C語言遞歸

1. 漢諾塔：

請輸入盤子數，輸出盤子移動的操作步驟。

#include
void move(char from, char to) {
   printf("%c to %cn", 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
intstair(intn) {
if (n==1) return1;
if (n==2) return2;
returnstair(n-1) +stair(n-2);
}
voidmain() {
intn;
scanf("%d", &n);
printf("%d", stair(n));
}

3. 爬樓梯：

樹老師爬樓梯，他可以每次走1級、2級或者3級，輸入樓梯的級數，求不同的走法數。

#include
intstair(intn) {
if (n==1) return1;
if (n==2) return2;
if (n==3) return4;
returnstair(n-1) +stair(n-2) +stair(n-3);
}
voidmain() {
intn;
scanf("%d", &n);
   printf("%d", stair(n));
}

4. 斐波那契數列：

請輸入項數，輸出具體數列。

#include
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
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
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
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");
  }
}

8. 求年齡：

有5個人坐在一起，問第5個人多少歲，他說比第4個人大2歲。問第4個人多少歲，他說比第3個人大2歲。問第3個人多少歲，他說比第2個人大2歲。問第2個人多少歲，他說比第1個人大2歲。最后問第1個人，他說是10歲。請問第5個人多大？

#include
int age(int n) {
   if (n == 1) return 10;
   return age(n - 1) + 2;
}
void main() {
   printf("%d", age(5));
}

9. 猴子吃桃問題：

猴子第一天摘下若干個桃子，當即吃了一半，還不癮，又多吃了一個。第二天早上又將剩下的桃子吃掉一半，又多吃了一個。以后每天早上都吃了前一天剩下的一半多一個。到第十天早上想再吃時，見只剩下一個桃子了。問最初有多少個桃子。

遞歸：

#include
int peach(int n) {
   if (n == 10) return 1;
   return (peach(n + 1) + 1) * 2;
}
void main() {
   printf("%d", peach(1));
}

循環：

#include
void main() {
   int i, s = 1;
   for (i = 9; i >= 1; i--) {
       s = (s + 1) * 2;
  }
   printf("%d", s);
}

10. 猴子吃桃問題：

猴子第一天摘下若干個桃子，當即吃了一半，還不癮，又多吃了一個。第二天早上又將剩下的桃子吃掉一半，又多吃了一個。以后每天早上都吃了前一天剩下的一半多一個。第十天同樣是吃了前一天的一半加一個，最后剩下一個桃子。問最初有多少個桃子。

遞歸：

#include
int peach(int n) {
   if (n == 11) return 1;
   return (peach(n + 1) + 1) * 2;
}
void main() {
   printf("%d", peach(1));
}

循環：

#include
void main() {
   int i, s = 1;
   for (i = 10; i >= 1; i--) {
       s = (s + 1) * 2;
  }
   printf("%d", s);
}

11. 最大公約數：

利用遞歸算法求兩個數的最大公約數。

#include
/* 最大公約數 */
int gcd(int a, int b) {
   int t;
   if (a < b) {
       t = a;
       a = b;
       b = t;
  }
   if (b == 0) {
       return a;
  }
   return gcd(b, a % b);
}
void main() {
   int a, b;
   scanf("%d%d", &a, &b);
   printf("gcd=%d", gcd(a, b));
}

12. 逆序輸出：

輸入一個正整數，將該正整數逆序輸出。

#include
void printDigit(int n) {
   printf("%d", n % 10);
   if (n > 10) {
       printDigit(n / 10);
  }
}
void main() {
   int n;
   scanf("%d", &n);
   printDigit(n);
}

13. 逆序輸出：

輸入一個字符串，將該字符串逆序輸出。

#include
void printStr(char *str) {
   if (*str != '?')
       printStr(str + 1);
   if (*str != '?')
       printf("%c", *str);
}
void main() {
   char str[100];
   gets(str);
   printStr(str);
}