苏州网站建设师,wordpress全站开启ssl,柳州做网站的企业,seo博客模板目录
前言
十、递归程序设计
10.1 计算n#xff01;——递归程序设计
10.2 程序设计实例
10.2.1 汉诺塔
10.2.2 齿轮
10.2.3 组合
10.3 计算算术表达式的值——间接递归
10.4 递归程序执行过程 前言 递归程序设计是一种编程技术#xff0c;其中一个函数通过调用自身…目录
前言
十、递归程序设计
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.hint 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.hvoid 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.hint 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.hint 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的问题因为堆栈的大小是有限的。
注意 递归终止条件的设置否则可能会导致无限递归使程序陷入死循环。递归程序还需要注意递归的效率因为递归调用会带来函数调用的额外开销。
