递归之原理及汉罗塔的递归与非递归实现[通俗易懂]

递归之原理及汉罗塔的递归与非递归实现[通俗易懂]递归章节一.什么是递归递归:简单的讲,就是定义一个过程或函数时出现调用本过程或本函数就称为递归。典型的例子:求阶乘:intfun(intn){ if(n==1) return(1);elsereturnfun(n*fun(n-1));}二.那么使用递归需要满足那些条件呢?(1) 从上例就可以看出,递归需要终止递归的结束条件。(2)…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

递归章节

一.什么是递归

递归:简单的讲,就是定义一个过程或函数时出现调用本过程或本函数就称为递归。
典型的例子:
求阶乘:

int fun(int n) { 
   
	if(n == 1)
		return(1);
   else
        return fun(n*fun(n - 1));
}

二.那么使用递归需要满足那些条件呢?

(1) 从上例就可以看出,递归需要终止递归的结束条件。
(2) 递归的次数必须是有限次的
(3) 可以将一个大的问题转化为一个或多个与原问题相似规模较小的子问题,而这些小问题求解方法与原问题相同。

三.可使用递归的一些情况:

1. 函数或过程定义是递归的。

如,Fibonacci数列:

int Fib(int n) { 
   
	if(n == 1 || n == 2)
		return (1);
    else
        return (Fib(n - 1) + Fib(n - 2));
}

2 问题求解方法是递归的

如,汉罗塔问题:

  1. 首先定义函数:Hanio(n,x,y,z) 表示将x上的n个盘子借助y移动到z上;
    将1这个问题分解:
    (1)想要把n个盘子从x移动到z,也就是需要把n-1个盘子从x借助z先移动到y上, 即:Hanio(n-1,x,z,y)
    (2) 此时x上只有第n个盘子,直接移动到z上,即:move(n,x,z)
    (3)递归调用,Hanio(n-1,y,x,z)
    注解: 事实上,这个很好理解,相信第一步和第二步很容易理解,第三步递归调用咋回事呢?
    我们定义的函数体是Hanio(n,x,y,z) 执行完第(1)、(2)之后变成什么结果呢?
    即:y这根柱子现在有n-1个盘子,z上是第n盘子,x没有盘子。
    此时我们将 n-1赋值给n,将y赋值给x,将z赋值给z不就是和初始化状态一模一样啦,只是少了一个盘子而已,我们调用函数重复第(1)、(2)步骤就OK了。即调用Hanio(n-1,y,x,z),现在是不是懂了啊!递归始终是将大规模问题简化,并且简化后的子问题和原问题求解方法相同。源代码如下:
void Hanio(int n, char x, char y, char z)
{ 
   
	if (n == 1)
		printf("第%d个盘子:%c-->%c\n", n, x, z); 
	else { 
   
		Hanio(n - 1, 'x', 'z', 'y');   // 此时x=x,y=y,z=z
		printf("第%d个盘子:%c-->%c\n", n, x, z);
		Hanio(n - 1, 'y', 'x', 'z');   //此时 x=y,y=z,z=z
	}
}

四.递归模型:

递归模型一般分为两部分:递归结束出口和递归体。在递归体过程中,一般分为两部分,对递归问题分解和求值两部分。
如 阶乘递归:以fun(5)为例
5的阶乘分解和求解过程Alt

递归模型的一般步骤:

(1) 首先,在大问题(第n个问题)假设合理的小问题(第n-1个问题)
(2) 确定n与n-1之间的关系,也就是确定递归体。
(3) 找到合理的出口,如n=0或者n=1时的解。

五.递归与栈

用栈来实现汉罗塔:

#include<stdio.h>
#include<iostream>
#include<cstdlib>
using namespace std;
#define Max 50
typedef struct { 

int n;  //表示有多少个盘子
char x;
char y;
char z;
bool move_flag;  //表示这个元素是否可以移动。 当n=1时是可以移动的
}ElemType;
typedef struct { 

ElemType data[Max];
int top;
}StackHanio;
//初始化栈
void InitStack(StackHanio &s) { 

s.top = -1;
}
//判断栈是否为空
bool Stackempty(StackHanio s){ 

return(s.top == -1);
}
//元素入栈
void Push(StackHanio &s, ElemType e) { 

if (s.top == Max - 1)
exit(1);
else{ 

s.top++;
s.data[s.top] = e;
}
}
//元素出栈
void Pop(StackHanio &s, ElemType &e) { 

if (s.top == -1)
exit(1);
else { 

e = s.data[s.top];
s.top--;
}
}
void Hanio(int n1, char x, char y, char z) { 

StackHanio s;
InitStack(s);
ElemType e, e1, e2, e3;
e.x = 'X', e.y = 'Y', e.z = 'Z', e.n = n1, e.move_flag = false;
Push(s, e);
while (!Stackempty(s)) { 

Pop(s,e);
if (e.move_flag == false) { 

e3.n = e.n - 1, e3.x = e.y, e3.y = e.x, e3.z = e.z;
if (e3.n == 1)
e3.move_flag = true;
else
e3.move_flag = false;
Push(s, e3);      //相当于Hanio(n-1,y,x,z)
e2.n = e.n, e2.x = e.x, e2.y = e.y, e2.z = e.z,e2.move_flag=true;
Push(s, e2);     //mov(n,x,z)
e1.n = e.n - 1, e1.x = e.x, e1.y = e.z, e1.z = e.y;
if (e1.n == 1)
e1.move_flag = true;
else
e1.move_flag = false;
Push(s, e1);    //Hanio(n-1,x,z,y)
}
else
cout << "第" <<e.n<<  "个盘片:" <<e.x<< "-->" << e.z << "\n";
}
}
int main() { 

Hanio(3, 'X', 'Y', 'Z');
system("pause");
return 0;
}

[注]: 如果我们用递归实现汉罗塔时:
将x上n个盘子借助y移动到z上
一般有以下三步:
(1)Hanio(n-1,x,z,y)
(2)mov(n,x,z)
(3)Hanio(n-1,y,x,z)
若使用栈时:由于栈是后进先出这种特性;
所以在代码实现时与递归实现的(1)和(3)反过来啦,请读者自行体会:
Alt

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/182998.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 锐捷交换机(S2924/2928G)光口改电口,或电口改光口的准确方法「建议收藏」

    锐捷交换机(S2924/2928G)光口改电口,或电口改光口的准确方法「建议收藏」软件需求:telnet。依次输入Ruijie&gt;输入enable//若未设置enable密码,需要在web中先设置Ruijie#输入configRuijie(config)#输入intg0/24//其中g代表千兆口,0/24代表24号端口Ruijie(config-if-GigabitEthernet0/24)#输入medium-typ…

  • Python之字典添加元素

    Python之字典添加元素手动推荐知识点字典创建->创建字典(7种方式)删除元素->字典删除元素(6种方式)修改元素->字典修改元素(4种方式)遍历元素->字典遍历元素(4种方式)查找元素->字典查找元素(3种方式)本文使用代码book_dict={“price”:500,”bookName”:”Python设计”,”weight”:”250g”}第一种方式:使用[]book_dict[“owner”]=”tyson”说明:中.

  • 【转载】秒杀系统架构优化思路

    【转载】秒杀系统架构优化思路

    2021年11月18日
  • 第十一单元作业

    第十一单元作业

  • Java事务管理[通俗易懂]

    Java事务管理[通俗易懂]事务的ACID属性:原子性(Atomicity)、一致性(Consistency)、隔离性或独立性(Isolation)和持久性(Durabilily)一、Java事务管理Java事务管理有三种类型:JDBC事务、JTA(JavaTransactionAPI)事务、容器事务1.1JDBC事务JDBC的一切行为包括事务是基于一个Connection的,JDBC通过Connec…

  • Tomcat8zip版本安装与配置[通俗易懂]

    Tomcat8zip版本安装与配置[通俗易懂]Tomcat8zip版本安装配置哈哈哈,又到了紧张刺激的每日必答:在开始之前呢,小Du来来带大家了解几个问题,希望能够在面试中,小Du的解答给你帮助。老样子,话不多说直接上图1.什么Tomcat:答:简单总结下,tomcat是一个中间件,在B/S架构中,浏览器发出的http请求经过tpmcat中间件,转发到最终的目的服务器上,响应消息再通过tomcat返回给浏览器。tomcat所做的事情主要有:开启监听端口监听用户的请求,解析用户发来的http请求然后访问到你指定的应用系统,然后你返回的页面经过t

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号