前言
递归程序设计是一种编程技术，其中一个函数通过调用自身来解决问题。递归的思想是将大问题划分为更小的子问题，并通过解决子问题来解决原始问题。递归可以在问题的规模较小的情况下，通过不断地调用自身来解决更大规模的问题。递归函数通常包含两个部分：基本情况和递归情况。
- 基本情况是指问题的规模已经足够小，不再需要进一步的递归调用，可以直接返回结果。这是递归的结束条件。
- 递归情况是指问题的规模仍然较大，需要通过调用自身来解决更小规模的子问题。递归函数在解决子问题时，会不断地调用自身，直到达到基本情况。
十、递归程序设计
10.1 计算n！——递归程序设计
要计算n的阶乘（n!），可以使用递归程序设计。递归计算n的阶乘的思路如下：
- 基本情况：当n为0或1时，阶乘的结果为1。
- 递归情况：当n大于1时，n的阶乘可以表示为n乘以(n-1)的阶乘。
#include <stdio.h>
int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
int main() {
int n = 5;
int result = factorial(n);
printf("%d! = %dn", n, result);
return 0;
}函数factorial是递归函数。它将问题划分为计算n乘以(n-1)的阶乘的子问题，并通过递归调用自身来解决子问题，直到达到基本情况。调用这个函数来计算任意正整数n的阶乘，例如factorial(5)将返回120。
10.2 程序设计实例
10.2.1 汉诺塔
汉诺塔是一个经典的递归问题。它涉及将一堆盘子从一个柱子移动到另一个柱子，每次只能移动一个盘子，并且大盘子不能放在小盘子上面。下面是一个用C语言实现汉诺塔问题的递归函数：
代码语言：javascript复制#include <stdio.h>
void hanoi(int n, char source, char destination, char auxiliary) {
if (n == 1) {
printf("Move disk 1 from %c to %cn", source, destination);
return;
}
hanoi(n - 1, source, auxiliary, destination);
printf("Move disk %d from %c to %cn", n, source, destination);
hanoi(n - 1, auxiliary, destination, source);
}
int main() {
int n = 3;
hanoi(n, 'A', 'C', 'B');
return 0;
} 函数hanoi用来解决汉诺塔问题。它接受四个参数：n表示盘子的数量，source表示源柱子，destination表示目标柱子，auxiliary表示辅助柱子。当n为1时，直接将盘子从源柱子移动到目标柱子。否则，它将递归地将n-1个盘子从源柱子移动到辅助柱子，然后将第n个盘子从源柱子移动到目标柱子，最后将n-1个盘子从辅助柱子移动到目标柱子。
10.2.2 齿轮
10.2.3 组合
组合是数学中的一个概念，指的是从一个给定的集合中选取一部分元素的方式。想要实现一个计算组合的程序，可以使用递归或迭代的方法：
代码语言：javascript复制#include <stdio.h>
int combination(int n, int k) {
if (k == 0 || k == n) {
return 1;
} else {
return combination(n - 1, k - 1) combination(n - 1, k);
}
}
int main() {
int n = 5;
int k = 3;
int result = combination(n, k);
printf("C(%d, %d) = %dn", n, k, result);
return 0;
} 函数combination用来计算组合。它接受两个参数：n和k，分别表示集合的大小和选取的元素个数。当k等于0或k等于n时，返回1，表示只有一种选取方式。否则，它将递归地计算从n-1个元素中选取k-1个元素的组合数，以及从n-1个元素中选取k个元素的组合数，并将它们相加作为结果。
10.3 计算算术表达式的值——间接递归
要计算算术表达式的值，可以使用间接递归来实现，间接递归是指多个函数之间相互调用形成的递归关系：
代码语言：javascript复制#include <stdio.h>
int expression_value(char* expression);
int factor_value(char* expression) {
if (expression[0] == '(') {
return expression_value(expression 1);
} else {
return expression[0] - '0';
}
}
int term_value(char* expression) {
int value = factor_value(expression);
if (expression[1] == '*') {
value *= term_value(expression 2);
}
return value;
}
int expression_value(char* expression) {
int value = term_value(expression);
if (expression[1] == ' ') {
value = expression_value(expression 2);
}
return value;
}
int main() {
char expression[] = "((2*3) 4)";
int result = expression_value(expression);
printf("Expression value: %dn", result);
return 0;
}- 我们定义了三个函数：
expression_value、term_value和factor_value，它们之间相互调用形成了间接递归。factor_value函数用来计算因子的值，如果因子是一个括号内的表达式，则调用expression_value函数来计算括号内表达式的值；否则，将字符转换为对应的数字。term_value函数用来计算项的值，首先计算第一个因子的值，然后判断后面是否有乘号，并乘以后面的因子的值。expression_value函数用来计算表达式的值，首先计算第一个项的值，然后判断后面是否有加号，并加上后面的项的值。
- 在
main函数中，定义一个算术表达式，并调用expression_value函数来计算表达式的值，并打印结果。
10.4 递归程序执行过程
递归程序的执行过程可以通过堆栈（stack）来理解。当一个函数被调用时，它的局部变量和函数调用的返回地址被压入堆栈。如果函数内部包含递归调用，那么每次递归调用都会将新的局部变量和返回地址压入堆栈。递归的结束条件是达到递归终止条件，此时递归开始回溯，从最后一个递归调用返回到上一个递归调用，然后再返回到更上一层递归调用，直到回到最初的函数调用。
在递归程序执行过程中，每个递归调用都会占用一些内存空间，并且会在堆栈上创建一个新的帧（frame），包含局部变量和返回地址。当递归调用过多时，可能会导致堆栈溢出（stack overflow）的问题，因为堆栈的大小是有限的。
- 注意
- 递归终止条件的设置，否则可能会导致无限递归，使程序陷入死循环。
- 递归程序还需要注意递归的效率，因为递归调用会带来函数调用的额外开销。
