递归
递归一个函数直接或间接调用自己的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归要满足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++中的递归函数的调用过程,即汉诺塔游戏的移动过程。
递归函数就是直接或间接调用自身的函数。 递归两要素:递归关系和递归边界(终止条件),递归关系确定了迭代的层次结构,需要深入了解并分解问题;终止条件保证了程序的有穷性。 递归的应用有很多,常见的包括:阶乘...
matlab递归实现汉诺塔m函数文件 压缩包中含有两个文件hannuota.m和hanoi.m 其中,hannuota.m无动画演示,调用格式为: >>hannuota(5,'A','B','C') hanoi.m有动态演示汉诺塔功能,是在hannuota.m的基础上实现,调用...
简单的函数递归调用,实现汉诺塔,每一个步骤,资源来自于c++程序语言设计上册
//程序实现了mystack栈的声明和定义,并且通过函数 //move_stacks的递归调用和函数move_a_ring实现汉 //诺塔的算法,并用函数print_stacks和pr_chars实现汉诺 //塔的动画效果
1、此程序为汉诺塔程序(此代码用到递归,包括直接递归和间接递归(间接递归是用在了重复使用本程序那块)); 2、此程序的代码流程是,由main函数进入之后,先后调用的函数是由上至下定义的; 3、亲爱的朋友,请...
解决汉诺塔问题, 用递归法将一个整数n转换成字符串。例如,如入483,应输出字符串“483”。N的位数不确定,可以是任意位整数。 1.3 建立一个包含加法函数、减法函数的动态链接库文件和一个包含加法函数、减法函数...
递归,简单来说,就是一个函数调用自身的过程。在汉诺塔问题中,为了将n个盘子从一根柱子移动到另一根柱子,我们需要先将n-1个盘子移动到辅助柱子上,然后将最大的盘子移动到目标柱子上,最后再将n-1个盘子从辅助...
该压缩包中包含了c语言实现的动态显示4阶汉诺塔代码和演示,有注释,界面友好,美观大方,里面有关于与光标移动的函数,也有着递归调用实现汉诺塔的方法,按道理来说,只要稍加修改,便可以实现所有的汉诺塔的演示。...
网上转载,对算法设计有兴趣的请慢慢研究
void hanoi(int n,int x,int y,int z) //打印移动盘子的函数,递归调用的 { if (n==1) //如果只有一个盘子,很简单,直接把盘子从X移动到Z就结束了 printf("%c-->%c\n",x,z); //打印“x-->z”,就是上面说的 else /...
深入理解 函数递归的调用
本文实例讲述了Python基于递归算法实现的汉诺塔与Fibonacci数列。分享给大家供大家参考,具体如下: 这里我们通过2个例子,学习python中递归的使用。 1. 找出Fibonacci数列中,下标为 n 的数(下标从0计数) ...
汉诺塔java源码Java 中解决河内塔之谜的递归方法 概述 递归是一个函数将自身作为子程序调用的过程。 这允许函数重复多次,因为它在执行期间调用自身。 包含递归的函数称为递归函数。 递归通常被视为一种有效的编程...
本文实例讲述了python实现的汉诺塔算法。分享给大家供大家参考,具体如下: 规则: 圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定 在小圆盘上不能放大圆盘 在三根柱子之间一次只能移动一个圆盘。 ...
1、 理解函数的定义、调用和参数传递的使用,以及函数的...2、 通过对实训的学习,可以理解函数作为功能模块在程序中的作用,把握函数调用机制。 3、 利用函数实现汉诺塔盘子的移动操作,并打印每次盘子的移动步骤。
//递归函数调用求汉诺塔之解 public static void HanoiTower(int n,char a,char b,char c){ if(n==1){ System.out.print("Move disk from" + a + " -> " + c + "\n"); }else { //将A上n-1个盘子借助C...
(汉诺塔问题) 这类问题虽则本身没有明显的递归结构,但用递归求解比迭代求解更简单,如Hanoi问题。 (3)数据的结构形式是按递归定义的。 如二叉树、广义表等,由于结构本身固有的递归特性,则它们的...
8.4.1 函数调用的一般形式 106 8.4.2 函数调用的方式 106 8.4.3 被调用函数的声明和函数原型 107 8.5 函数的嵌套调用 108 8.6 函数的递归调用 109 8.7 数组作为函数参数 110 8.8 局部变量和全局变量 112 8.8.1 局部...