【重拾C语言】十、递归程序设计

前言

十、递归程序设计

10.1 计算n！——递归程序设计

10.2 程序设计实例

10.2.1 汉诺塔

10.2.2 齿轮

10.2.3 组合

10.3 计算算术表达式的值——间接递归

10.4 递归程序执行过程

前言

递归程序设计是一种编程技术，其中一个函数通过调用自身来解决问题。递归的思想是将大问题划分为更小的子问题，并通过解决子问题来解决原始问题。递归可以在问题的规模较小的情况下，通过不断地调用自身来解决更大规模的问题。递归函数通常包含两个部分：基本情况和递归情况。

基本情况是指问题的规模已经足够小，不再需要进一步的递归调用，可以直接返回结果。这是递归的结束条件。
递归情况是指问题的规模仍然较大，需要通过调用自身来解决更小规模的子问题。递归函数在解决子问题时，会不断地调用自身，直到达到基本情况。

十、递归程序设计

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! = %d\n", n, result);return 0;
}

函数factorial是递归函数。它将问题划分为计算n乘以(n-1)的阶乘的子问题，并通过递归调用自身来解决子问题，直到达到基本情况。调用这个函数来计算任意正整数n的阶乘，例如factorial(5)将返回120。

10.2 程序设计实例

10.2.1 汉诺塔

汉诺塔是一个经典的递归问题。它涉及将一堆盘子从一个柱子移动到另一个柱子，每次只能移动一个盘子，并且大盘子不能放在小盘子上面。下面是一个用C语言实现汉诺塔问题的递归函数：

#include <stdio.h>void hanoi(int n, char source, char destination, char auxiliary) {if (n == 1) {printf("Move disk 1 from %c to %c\n", source, destination);return;}hanoi(n - 1, source, auxiliary, destination);printf("Move disk %d from %c to %c\n", 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 组合

组合是数学中的一个概念，指的是从一个给定的集合中选取一部分元素的方式。想要实现一个计算组合的程序，可以使用递归或迭代的方法：

#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) = %d\n", n, k, result);return 0;
}

函数combination用来计算组合。它接受两个参数：n和k，分别表示集合的大小和选取的元素个数。当k等于0或k等于n时，返回1，表示只有一种选取方式。否则，它将递归地计算从n-1个元素中选取k-1个元素的组合数，以及从n-1个元素中选取k个元素的组合数，并将它们相加作为结果。

10.3 计算算术表达式的值——间接递归

要计算算术表达式的值，可以使用间接递归来实现，间接递归是指多个函数之间相互调用形成的递归关系：

#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: %d\n", 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）的问题，因为堆栈的大小是有限的。