20 递归算法精髓解析：基准、性质、案例（阶乘、斐波拉契、猴子吃桃、汉诺塔等）、与循环的对比

1 概述

2 递归的基本组成部分

2.1 基准情况

2.2 递归步骤

2.3 案例：循环实现阶乘的计算

2.4 案例：递归函数实现阶乘的计算

3 递归的性质

3.1 自我调用

3.2 栈的使用

3.3 问题分解

3.4 性能考虑

3.5 案例：递归的回溯

4 综合案例

4.1 计算斐波那契数列的第 N 项

4.1.1 循环实现

4.1.2 递归函数实现

4.2 输出斐波那契数列的前 N 项

4.3 逆推猴子吃桃问题

4.4 汉诺塔问题

4.5 反转字符串

4.6 求数字之和

4.6.1 循环实现

4.6.2 递归函数实现

4.7 求两个数的最大公约数（辗转相除法）

4.7.1 循环实现

4.7.2 递归函数实现

5 递归与循环的区别与联系

5.1 区别

5.2 联系

1 概述

在 C 语言中，递归是一种编程技术，它允许一个函数直接或间接地调用自身。递归函数通常用于解决那些可以被分解为更小的子问题的问题，这些子问题具有与原始问题相同的结构。递归函数的设计需要特别小心，以确保递归最终能够终止，并且每一步都朝着解决最终问题的方向前进。

2 递归的基本组成部分

2.1 基准情况

基准情况（Base Case）是递归函数中的特殊条件，当满足这些条件时，函数将停止调用自身并直接返回一个结果。它是递归的出口，防止了无限递归的发生。每个递归函数都必须明确指定至少一个基准情况（即必须有一个明显的结束条件），这些情况是问题最简单或最直接的解决方案，无需进一步递归。

如在 2.4 案例：递归实现阶乘的计算中，基准情况可以是 n == 0 或 n == 1，因为 0 的阶乘和 1 的阶乘都定义为 1，这是可以直接给出的答案。

2.2 递归步骤

递归步骤（Recursive Step）是函数调用自身以解决更小或更简单问题的过程。在这一步中，函数通过某种方式减小问题的规模，使其更接近基准情况。递归步骤的设计至关重要，因为它必须确保每次递归调用都朝着基准情况的方向前进，即问题规模逐渐减小，复杂度逐渐降低，最终递归结束。

如在 2.4 案例：递归实现阶乘的计算中，递归步骤是 factorial(n) = n * factorial(n-1)。这里，每次调用 factorial 时，都通过减小 n 的值来缩小问题的规模，直到达到基准情况 n == 0 或 n == 1。这个过程体现了递归步骤如何确保问题规模趋近于基准条件，并最终导致递归的终止。

2.3 案例：循环实现阶乘的计算

#include <stdio.h>int factorial(int n)
{// result 初始设置为 1，因为任何数的阶乘乘以 1 都不会改变其值// 且 0 和 1 的阶乘就是 1int result = 1;// 从 2 遍历到 n（包括 n ），并在每次迭代中将当前的 result 乘以循环变量 ifor (int i = 2; i <= n; i++){result *= i;}// 返回最终结果return result;
}int main()
{int number = 0;printf("请输出一个需要计算其阶乘的非负整数：");scanf("%d", &number);// 验证输入数据的合法性if (number >= 0){printf("%d 的阶乘是： %d\n", number, factorial(number));}else{printf("对于负数，阶乘是未定义的。\n");}return 0;
}

在 CMD 中多次运行程序，输出结果如下所示：

2.4 案例：递归函数实现阶乘的计算

#include <stdio.h>// 递归函数来计算阶乘
long factorial(int n)
{// 基准情况：递归的出口if (n == 0 || n == 1) // 或者 if(n <=1 ){return 1;}// 递归步骤:调用自身以解决更小或更简单问题的过程，使其更接近基准情况else{return n * factorial(n - 1);}
}int main()
{int number = 0;printf("请输出一个需要计算其阶乘的非负整数：");scanf("%d", &number);// 验证输入数据的合法性if (number >= 0){printf("%d 的阶乘是： %ld\n", number, factorial(number));}else{printf("对于负数，阶乘是未定义的。\n");}return 0;
}

在 CMD 中多次运行程序，输出结果如下所示：

以 factorial(5) 为例，递归函数结构分析如下所示：

提示：

还可以在程序的关键位置设置断点，通过调试工具逐步执行，来深入探究递归函数的运行情况。

3 递归的性质

3.1 自我调用

递归函数在其定义内部调用自身。这是递归的核心特性。通过自我调用，函数能够不断地将问题分解为更小的子问题，直到达到一个基准情况（或称为基本情况、边界条件），此时函数将停止调用自身并返回一个结果。

3.2 栈的使用

在 C 语言中（以及大多数其他编程语言中），函数调用是通过栈来实现的。当函数被调用时，它的执行环境（包括局部变量、参数、返回地址等）会被压入调用栈中。递归调用也不例外，每次递归调用都会创建一个新的栈帧（stack frame），并压入调用栈。当递归函数开始返回时，这些栈帧会按照后进先出（LIFO）的顺序被弹出，从而实现了从最深递归层次开始回溯到最初调用的过程。

3.3 问题分解

递归调用的过程实际上是一个问题分解的过程。每次递归调用都将原问题分解为一个或多个更小的子问题，直到子问题变得足够简单，可以直接解决（即达到基准情况）。然后，递归函数通过组合这些子问题的解来得到原问题的解。

3.4 性能考虑

虽然递归调用在解决某些问题时非常直观和方便，但它也可能导致性能问题。特别是当递归深度很大时，由于需要大量的栈空间来存储每次调用的执行环境，这可能会导致栈溢出错误。此外，递归调用还可能引入额外的函数调用开销。

3.5 案例：递归的回溯

#include <stdio.h>// 函数声明，用于演示递归调用并打印数字
void test(int n)
{// 首先打印当前传入的数字printf("%d\n", n);// 检查 n 是否大于 1，如果是，则递归调用自身并传入 n-1if (n > 1){test(n - 1);}// 递归返回后，再次打印当前数字（此时是从最深的递归层次返回时打印）printf("%d\n", n);
}int main()
{// 调用 test 函数，传入数字 3 作为参数// 这将展示递归函数如何工作，并打印出特定的数字序列test(3);return 0;
}

输出结果如下所示：

程序分析如下所示：

上面这个程序演示了一个简单的递归函数 test，它接受一个整数 n 作为参数。函数首先打印当前的 n 值，然后检查 n 是否大于 1。如果是，则递归调用自身，但传入的参数是 n-1。这导致了一个递归过程，其中数字被连续减小并打印，直到 n 不再大于 1，此时递归调用停止。但是，由于递归调用的性质，函数在返回过程中还会再次打印每个数字，这次是从最深的递归层次开始回溯到最初的调用。因此，对于给定的输入 3，输出将是 3、2、1（递减过程），然后是1、2、3（回溯过程）。

4 综合案例

4.1 计算斐波那契数列的第 N 项

斐波那契数列是指这样一个数列：1，1，2，3，5，8，13，21，34，55，89……这个数列从第 3 项开始，每一项都等于前两项之和。现在要求编写一个程序，接收用户输入的一个正整数 n，然后输出斐波那契数列的第 n 项。

4.1.1 循环实现

下面是通过 for 循环结构来实现斐波那契数列第 n 项计算的程序示例：

#include <stdio.h>// 函数原型声明
int fibonacci(int n);int main()
{int n;printf("请输入一个正整数n，以获取斐波那契数列的第n项: ");scanf("%d", &n);// 检查输入值是否合法if (n < 1){printf("输入的数字必须大于等于1。\n");return 1; // 退出程序}// 调用函数并打印结果printf("斐波那契数列的第%d项是: %d\n", n, fibonacci(n));return 0;
}// 使用循环实现斐波那契数列第 n 项的函数
int fibonacci(int n)
{if (n == 1 || n == 2){// 如果 n 是 1 或 2，则直接返回 1return 1;}// 初始化第一项和第二项int first = 1, second = 1, third;// 从3 开始循环遍历for (int i = 3; i <= n; i++){third = first + second; // 计算前两项之和first = second;         // 更新 first 为前一项second = third;         // 更新 second 为当前项（即前两项之和）}return second; // 循环结束后，second 中存储的就是第 n 项的值
}

在 CMD 中多次运行程序，输出结果如下所示：

4.1.2 递归函数实现

下面是通过递归函数来实现斐波那契数列第 n 项计算的程序示例：

#include <stdio.h>// 函数原型声明
int fib(int n);int main()
{int n;printf("请输入一个正整数n，以获取斐波那契数列的第n项: ");scanf("%d", &n);// 检查输入值是否合法if (n < 1){printf("输入的数字必须大于等于1。\n");return 1; // 退出程序}// 调用 fib 函数计算斐波那契数列的第 n 项，并输出结果printf("%d 的斐波那契数是：%d\n", n, fib(n));return 0;
}// 函数声明：计算斐波那契数列的第 n 项
int fib(int n)
{// 基准情况：如果 n 是 1 或 2，则斐波那契数为 1if (n == 1 || n == 2) // 或者 if (n <= 1){return 1;}// 递归情况：斐波那契数列的第 n 项是第 n-1 项和第 n-2 项之和else{return fib(n - 1) + fib(n - 2);}
}

在 CMD 中多次运行程序，输出结果如下所示：

4.2 输出斐波那契数列的前 N 项

现在要求编写一个程序，程序接收一个整数 n 作为输入，并输出斐波那契数列的前 n 项。

#include <stdio.h>// 函数声明：计算斐波那契数列的第 n 项
int fib(int n);int main()
{int n;printf("请输入一个正整数n，以获取斐波那契数列的第n项: ");scanf("%d", &n);// 检查输入值是否合法if (n < 1){printf("输入的数字必须大于等于1。\n");return 1; // 退出程序}// 循环输出斐波那契数列的前 n 项for (int i = 1; i <= n; i++){printf("%d ", fib(i)); // 调用 fib 函数并打印结果}printf("\n");return 0;
}// 函数声明：计算斐波那契数列的第 n 项
int fib(int n)
{// 基准情况：如果 n 是 1 或 2，则斐波那契数为 1if (n == 1 || n == 2) // 或者 if (n <= 1){return 1;}// 递归情况：斐波那契数列的第 n 项是第 n-1 项和第 n-2 项之和else{return fib(n - 1) + fib(n - 2);}
}

在 CMD 中多次运行程序，输出结果如下所示：

4.3 逆推猴子吃桃问题

有一堆桃子，猴子第一天吃了其中的一半，并多吃一个。以后每天猴子都吃其中的一半，然后再多吃一个。当到第十天早晨，猴子想再吃时（注意：此时还没吃），发现只有 1 个桃子了。问：最初共多少个桃子？

题目分析：根据题意，第 10 天早晨还剩下最后 1 个桃子，这意味着第 9 天猴子吃完桃子后，实际上只剩下了这 1 个桃子。因此，在第 9 天早晨（猴子还未吃桃前），桃子的数量应当是第 10 天早晨剩余桃子数量（1 个）加上 1，然后乘以 2 的结果。据此，第 9 天早晨桃子的数量为 (1+1)*2=4 ；同样地，第 8 天早晨（猴子还未吃桃前）的桃子数量可以通过第 9 天早晨（猴子还未吃桃前）的桃子数量来计算：(4+1)*2=10。以此类推，【当天桃子的初始数量=(明天桃子的初始数量 + 1)* 2 ，即 f(day) = [f(day+1)+1]*2】我们可以通过这种方法一直逆推回去，直到求得第 1 天早晨最初的桃子数量。

为了实现这一逻辑，我们可以编写一个递归函数来帮助计算。

#include <stdio.h>// 定义递归函数，参数 day 表示当前计算的是第几天的桃子数量
int peachCount(int day)
{if (day == 10){ // 如果达到第 10 天，直接返回 1（题目已知条件）return 1;}else{// 前一天的初始桃子数量=(当天的初始桃子数量 + 1)* 2 ，即 f(day) = [f(day+1)+1]*2return (peachCount(day + 1) + 1) * 2;}
}int main()
{printf("第十天开始时桃子的数量（验证基准情况）： %d \n", peachCount(10));// 第九天开始时的桃子数量printf("第九天开始时桃子的数量： %d \n", peachCount(9));// ... 以此类推，直到第一天printf("最初共有桃子 %d 个。\n", peachCount(1));return 0;
}

输出结果如下所示：

4.4 汉诺塔问题

汉诺塔（Tower of Hanoi）是一个源于印度古老传说的经典递归问题。它包含三根柱子和一系列不同大小的圆盘，这些圆盘原本按照大小顺序穿在一根柱子上，并且大的圆盘在下面，小的圆盘在上面。目标是将这些圆盘移动到另一根柱子上，同时满足以下规则：

每次只能移动一个圆盘。
在任何时候，较大的圆盘都不能放在较小的圆盘上面。
可以使用第三根柱子作为辅助。

#include <stdio.h>// 函数声明
void hanoi(int n, char from_rod, char to_rod, char aux_rod);int main()
{int n;printf("请输入圆盘的数量: ");scanf("%d", &n);// 假设有三个柱子分别命名为 'A', 'B', 'C'// 我们需要将圆盘从柱子 A 移动到柱子 C，使用柱子 B 作为辅助printf("\nA:起始柱子 B: 辅助柱子 C:目标柱子\n");printf("A:起始柱子上的圆盘，从上到下（小盘到大盘），编号为： 1 2 3 …… n\n");printf("步骤如下所示：");hanoi(n, 'A', 'C', 'B');return 0;
}// 汉诺塔问题的递归实现
/*** @brief 使用递归函数解决汉诺塔问题** @param n 圆盘的数量* @param from_rod 起始柱子* @param to_rod 目标柱子* @param aux_rod 辅助柱子，递归时可以拿其他柱子当辅助，即参数顺序可以按照需要变化*/
void hanoi(int n, char from_rod, char to_rod, char aux_rod)
{if (n == 1){// 当只有一个圆盘时，直接将其从起始柱子移动到目标柱子printf("\n  移动圆盘 1 号从 %c 到 %c", from_rod, to_rod);return;}// 将上面的 n-1 个圆盘从起始柱子移动到辅助柱子hanoi(n - 1, from_rod, aux_rod, to_rod);// 将最大的圆盘（第 n 个）移动到目标柱子printf("\n  移动圆盘 %d 号从 %c 到 %c", n, from_rod, to_rod);// 最后将 n-1 个圆盘从辅助柱子移动到目标柱子hanoi(n - 1, aux_rod, to_rod, from_rod);
}

当只有一个圆盘时，直接将其从起始柱子移动到目标柱子。

程序输出结果如下所示：

当只有两个圆盘时，圆盘移动步骤如下图所示：

程序输出结果如下所示：

当只有三个圆盘时，圆盘移动步骤如下图所示：

程序输出结果如下所示：

4.5 反转字符串

编写一个递归函数来反转一个字符串。例如，输入字符串 "hello"，输出 "olleh"。

#include <stdio.h>
#include <string.h>// 声明递归函数
void reverseString(char *str, int start, int end);int main()
{char str[] = "hello";int length = strlen(str);printf("反转之前的字符串为: %s\n", str);// 调用递归函数，注意结束索引为 length-1reverseString(str, 0, length - 1);printf("反转之后的字符串为: %s\n", str);return 0;
}// 递归函数定义
/*** @brief 反转字符串** 该函数使用递归方式反转字符串中从 start 索引到 end 索引（包含）之间的字符。* 注意，字符串的索引从 0 开始，因此 start 通常是 0，而 end 是字符串长度减 1。** @param str 指向要反转的字符串的指针* @param start 反转开始的索引（包含）* @param end 反转结束的索引（包含）** 注意：该函数会直接修改传入的字符串。*/
void reverseString(char *str, int start, int end)
{// 递归终止条件if (start >= end){return;}// 交换字符char temp = str[start];str[start] = str[end];str[end] = temp;// 递归调用，只改变 start 的值reverseString(str, start + 1, end);
}

输出结果如下所示：

4.6 求数字之和

输入一个非负整数，返回组成它的数字之和。例如，对于输入 1234，输出为 1+2+3+4=10。

4.6.1 循环实现

#include <stdio.h>// 函数声明
int sumOfDigits(int n);int main()
{int num;printf("请输入一个非负整数: ");scanf("%d", &num);                            // 读取用户输入的非负整数printf("数字之和为: %d\n", sumOfDigits(num)); // 调用函数并打印结果return 0;
}// 使用循环实现计算数字之和的函数
int sumOfDigits(int n)
{int sum = 0; // 初始化总和为 0while (n > 0){                  // 当 n 大于 0 时循环sum += n % 10; // 将 n 的最低位加到 sum 上n /= 10;       // 去掉 n 的最低位}return sum; // 返回总和
}

输出结果如下所示：

4.6.2 递归函数实现

#include <stdio.h>// 函数声明
int sumOfDigits(int num);int main()
{int num;printf("请输入一个非负整数: ");scanf("%d", &num);                            // 读取用户输入的非负整数printf("数字之和为: %d\n", sumOfDigits(num)); // 调用函数并打印结果return 0;
}// 使用递归实现计算数字之和的函数
/*** @brief 计算一个非负整数的各位数字之和** @param num 要计算的整数* @return 整数各位数字之和*/
int sumOfDigits(int num)
{// 递归终止条件：当 num 为 0 时，说明所有位数都已经被加过了if (num == 0){return 0;}// 递归调用，传入 num 除以 10 的结果（去掉最低位），并加上 num 的最低位（num % 10）return sumOfDigits(num / 10) + (num % 10);
}

程序分析图如下所示：

4.7 求两个数的最大公约数（辗转相除法）

最大公约数是两个或多个整数共有的最大的那个正整数约数。欧几里得算法（也称为辗转相除法）是求解两个或多个整数的最大公约数（GCD，Greatest Common Divisor）的一种高效算法。

欧几里得算法（也称为辗转相除法）的基本步骤是：对于两个正整数 a 和 b（假设 a > b），

计算 a 除以 b 的余数，记为 r。
如果 r 等于 0，则 b 就是 a 和 b 的最大公约数。
如果 r 不等于 0，则将 b 的值赋给 a，将 r 的值赋给 b，然后回到步骤 1。

这个过程会重复进行，直到余数为 0，此时，最后的非零除数就是两个数的最大公约数。

以求 98 56 的最大公约数为例：98 / 56 = 1……42（余数）
56 / 42 = 1……14（余数）
42 / 14 = 3……0（余数）或者56 / 98 = 0………56（余数）
98 / 56 = 1……42（余数）
56 / 42 = 1……14（余数）
42 / 14 = 3……0（余数）所以 98 和 56 的最大公约数是 14

4.7.1 循环实现

根据欧几里得算法的基本思想，可以通过在循环内部动态交换变量的值，不断地用较大的数除以较小的数，并取其余数，直到余数为零，从而逐步求出最大公约数。

#include <stdio.h>// 使用循环实现欧几里得算法
int gcd(int a, int b)
{while (b != 0){// 计算余数int r = a % b;// 交换数据a = b;b = r;}return a;
}int main()
{int num1, num2;// 输入两个数printf("请输入两个整数（用空格分隔）: ");scanf("%d %d", &num1, &num2);// 调用 gcd 函数并打印结果printf("%d 和 %d 的最大公约数是: %d\n", num1, num2, gcd(num1, num2));return 0;
}

输出结果如下所示：

4.7.2 递归函数实现

使用递归函数实现欧几里得算法来计算两个数的最大公约数（GCD）是一种既经典又高效的解决方案，它通过递归调用简化问题规模，直至找到最大公约数。

#include <stdio.h>// 递归函数实现欧几里得算法
int gcd(int a, int b)
{// 基本情况：当 b 为 0 时，a 即为两数的最大公约数if (b == 0){return a;}// 递归调用，计算 b 和 a%b 的最大公约数return gcd(b, a % b);
}int main()
{int num1, num2;// 输入两个数printf("请输入两个整数（用空格分隔）: ");scanf("%d %d", &num1, &num2);// 调用 gcd 函数并打印结果printf("%d 和 %d 的最大公约数是: %d\n", num1, num2, gcd(num1, num2));return 0;
}

输出结果如下所示：