递归
递归一个函数直接或间接调用自己的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归要满足3个条件:一是递归必须得有一个明确的中止条件,要不然就很可能陷入死递归;二是递归函数所处理数据(或问题)的规模必须在递减,n个问题的解决依赖于n-1个问题的解决;三是这个转化必须是可解的。
函数的调用机制
当在一个函数的运行期间调用另一个函数时,在运行被调函数之前,系统需要完成三件事:
a).将所有的实际参数,返回地址(下一条语句的地址)等信息传递给被调函数保存;
b).为被调函数的局部变量(也包括形参)分配存储空间;
c).将控制权限转移到被调函数的入口;
从被调函数返回主调函数之前,系统也要完成三件事:
a>.保存被调函数的返回的结果;
b>.释放被调函数所占的存储空间;
c>.依照被调函数保存的返回地址将控制权限转移到调用函数。
当多个函数相互调用时,按照“后调用先返回”的原则,上述函数之间信息传递和控制权限转移必须借助
“栈”来实现,即系统将整个程序运行时所需的数据空间安排在一个栈中,每当调用一个函数时,就在栈
顶分配一块存储区,进行压栈操作;每当一个函数退出时,就释放它的存储区,进行出栈操作,当前运行
的函数永远都在栈顶位置!
在计算机看来,A函数调用A函数和A函数调用B函数本质上是一样的。每调用一个函数,进行压栈操作;每
当函数退出时,就释放它的存储区就行出栈操作,当前运行的函数永远都在栈顶位置。
循环和递归的比较
递归优点:易于理解(问题规模原来可以转化为范围越来越小的问题)
递归缺点:速度慢(由函数调用机制决定,每次递归都得调自己),存储空间大(浪费空间很大)
循环优点:速度相对快 ,存储空间小(浪费空间很小)
循环缺点:不易理解(很多算法需要我们一个一个去推)
所有的循环都可以用递归实现,但所有的递归不一定可以用循环实现。
汉诺塔问题
问题描述:如何把A柱(第一根柱子)上面的n个盘子借助B柱(第二根柱子)移到C柱(第三根柱子)上?,且一次只能移动一个盘子,移动过程中小盘子必须始终放在大盘子上面(最下面的盘子编号最大)。
伪算法:1.当A柱子上只有1个盘子时,可直接将A柱上的盘子移到C柱
2.当A柱子上的盘子为n个时(n>1),此时可利用递归的思想分3步解决:
1).将A柱上的n-1个盘子借助C柱移到B柱;
2).将A柱上的第n个盘子直接移到C柱上;
3).将B柱上的n-1个盘子借助A柱移到C柱上;
递归算法实现(规定柱子上至少有一个盘子):
#include<stdio.h>
void Hanoitower(int n,char A,char B,char C)
{
if(1==n)
{
printf("将编号为%d的盘子从%c柱移到%c柱上\n",n,A,C);
}
else
{
Hanoitower(n-1,A,C,B);
printf("将编号为%d的盘子从%c柱移到%c柱上\n",n-1,A,C);
Hanoitower(n-1,B,A,C);
}
}
int main()
{
int n;
printf("请输入盘子的个数:");
scanf("%d",&n);
Hanoitower(n,'A','B','C');
return 0;
}
由盘子转移的次数可以推算出:汉诺塔的复杂度是2的n次方-1。
结束语
递归在很多地方用到,如树、图都是以递归的方式定义的。递归为我们解决复杂问题提供了方面(但这基本上是数学上的问题,所以理解要它的逻辑有时会很难)。学线性结构(数组、链表及其应用的栈、队列等)、递归及它们思想主要是为以后方面我们能将非线性问题转化为线性问题,进而通过线性结构的方法及思想来解决非线性结构问题。
分享到:
相关推荐
以下是一个C++实现汉诺塔问题的递归函数示例: ```cpp #include void hanoiTower(int n, char from_rod, char to_rod, char aux_rod) { if (n >= 1) { // 将n-1个盘子从from_rod移动到aux_rod hanoiTower(n - ...
总之,非递归的汉诺塔问题C++实现是一种创新的解决方案,它利用数据结构来避免递归调用的开销,展示了算法设计的灵活性和创造性。通过学习这种实现,你可以更深入地理解数据结构、算法以及它们在实际编程中的应用。
然后,使用递归函数 move 来解决汉诺塔问题。move 函数将汉诺塔问题分解成更小的子问题,然后将这些子问题解决后再将结果组合起来。 HanNoTa 图形解法的实现中还使用了文件指针 TEMP 来存储递归函数的输出结果。...
汉诺塔问题是一个经典的计算机科学问题,源自印度的古老传说,它涉及到三个柱子和一堆大小不一的圆盘。目标是将所有圆盘从一个柱子(称为起始柱)移动到另一个柱子(称为目标柱),同时遵循以下三个规则: 1. 每次...
汉诺塔问题是一个经典的计算机科学问题,通常使用递归算法来解决。然而,这个实验报告提出了使用非递归算法来解决汉诺塔问题的方法。非递归算法的关键在于找到一个可重复执行的步骤序列,而不是像递归那样通过自我...
在C++中,实现汉诺塔游戏通常会用到递归函数。递归是一种函数调用自身的技术,通过不断缩小问题规模直至达到基本情况来解决问题。在汉诺塔问题中,递归的基本情况是当盘子数量为1时,可以直接将盘子从源柱移动到目标...
汉诺塔问题是一个经典的递归算法问题,它涉及到三个柱子(塔)和若干个大小不一的圆盘。在初始状态下,所有圆盘按照大小顺序堆叠在第一个柱子(1号塔)上,大的在下,小的在上。目标是将所有的圆盘从1号塔移动到2号...
在C语言中,汉诺塔问题的解决通常采用递归函数来实现。递归函数的关键在于找到递归的基本情况(base case)和递归的分解过程(recursive case)。 #### 基本情况(Base Case) 当只有一个盘子时,直接将其从起始...
### 递归实现:汉诺塔问题 #### 经典问题背景 汉诺塔(Hanoi Tower)问题是一个经典的递归问题,源自一个古老的故事。传说在印度的一个神殿里,有三根金刚石柱子,第一根柱子上自上而下按大小顺序叠着64个金盘。...
* 在汉诺塔问题的解决方案中,需要遵循递归函数的调用规则,包括函数的参数、返回值和递归调用。 在实际应用中,汉诺塔问题的解决方案可以应用于各种领域,例如操作系统、数据库管理系统和人工智能。同时,汉诺塔...
**递归函数** 是解决汉诺塔问题的关键工具。递归是一种编程技术,它通过调用自身来解决问题。在汉诺塔问题中,我们可以定义一个递归函数来表示将n个盘子从柱子A移动到柱子C的过程,同时使用柱子B作为辅助。这个过程...
在MATLAB中,我们可以通过定义一个递归函数来解决这个问题。这个函数接受三个参数:当前塔(A或B),目标塔(C),以及辅助塔(B或C)。当只有一个圆盘时,我们直接将其从当前塔移动到目标塔。如果有多个圆盘,则先...
递归函数通常包括两个部分:递归调用和基本情况处理。 在汉诺塔程序中,可能会有一个主函数`hanoi(n, source, auxiliary, target)`,其中`n`是盘子的数量,`source`是起始柱子,`auxiliary`是辅助柱子,`target`是...
总的来说,汉诺塔问题的解决方案结合了递归算法和Java Swing的图形化能力,提供了一种直观的方式来理解和演示这一经典问题。在Eclipse中实现这样的程序,可以帮助学习者深入理解递归思想,并掌握如何在实际项目中...
**汉诺塔问题**是另一个著名的递归问题,涉及三根柱子及不同大小的圆盘。初始时所有圆盘按大小顺序堆叠在第一根柱子上,任务是将所有圆盘移动到第三根柱子上,同时保持大盘在小盘之下。 **关键知识点**: - **状态...
在C++中,递归可以有效地处理复杂的问题,但需要注意的是,递归可能导致大量的函数调用,如果递归深度过大,可能会消耗大量内存并可能导致栈溢出。因此,在实际编程中,对于大规模问题,可能需要考虑使用非递归的...
# 调用函数,开始汉诺塔问题的解 hanoi(3, 'A', 'B', 'C') ``` 在这个例子中,我们假设初始有3个盘子,分别位于柱子A上,目标是将它们全部移动到柱子C,同时使用柱子B作为辅助。输出会显示每一步的移动情况。 在...
汉诺塔游戏是一种经典的逻辑谜题,源自印度的古老传说,玩家需要将一系列盘子从一个柱子移动到另一个...对于C语言初学者来说,通过编写汉诺塔程序,不仅可以熟悉递归,还能提高对指针和函数调用的理解,提升编程技巧。
以下是一个用C语言实现的汉诺塔递归函数的示例: ```c #include void hanoi(int n, char from_rod, char to_rod, char aux_rod) { if (n > 0) { // 将n-1个圆盘从from_rod移动到aux_rod hanoi(n - 1, from_rod...
汉诺塔问题是一个著名的计算机科学问题,源自印度的古老传说,它涉及到三个柱子和一组盘子,每个盘子大小不一。问题的目标是将所有盘子从初始柱子(通常称为A柱)移动到目标柱子(C柱),遵循以下规则: 1. 每次...