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

递归之原理及汉罗塔的递归与非递归实现[通俗易懂]递归章节一.什么是递归递归:简单的讲,就是定义一个过程或函数时出现调用本过程或本函数就称为递归。典型的例子:求阶乘: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)


相关推荐

  • java messagedigest_Java 自带的加密类MessageDigest类(加密MD5和SHA)[通俗易懂]

    java messagedigest_Java 自带的加密类MessageDigest类(加密MD5和SHA)[通俗易懂]转载转载自:http://www.tuicool.com/articles/nMNVVjJava自带的数据加密类MessageDigest(MD5或SHA加密)说明:在网站中,为了保护网站会员的用户名和密码等隐私信息,所以我们在用户注册时就直接进行MD5方式或其他方式进行加密,即使是数据库管理员也不能查看该会员的密码等信息,在数据库中查看密码效果如:8e830882f03b2cb84d1a6…

  • 【Python秒杀脚本】淘宝或京东等秒杀抢购

    【Python秒杀脚本】淘宝或京东等秒杀抢购提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章目录前言一、环境二、安装1.ChromeDriver安装2.Seleuinm安装3.淘宝秒杀脚本4.京东秒杀脚本总结前言提示:这里可以添加本文要记录的大概内容:我们的目标是秒杀淘宝或京东等的订单,这里面有几个关键点,首先需要登录淘宝或京东,其次你需要准备好订单,最后要在指定时间快速提交订单。这里就要用到一个爬虫利器Selenium,Selenium是一个用于Web应用程序测试的工具,Selenium可以直接运行在浏览器中,通.

  • CSS样式表的使用

    CSS样式表的使用在用html5写网页的时候,结合CSS能够让页面更美观。由于只在做课程设计和实习的时候使用过,并没有系统的学习过,使得自己对于CSS的使用一直处于能用,但是容易弄混的阶段。为了弄清楚CSS样式表的使用,特地看书系统学习,现总结如下:CSS是通过选择器对不同的HTML标签进行控制,从而实现各种效果。常用的CSS选择器有标签选择器、类别选择器、id选择器。标签选择器的使用HTML网页是由很…

  • idea2021.3 激活码(JetBrains全家桶)

    (idea2021.3 激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html1STL5S9V8F-eyJsaWNlbnNlSW…

  • we7源码网站_源码论坛

    we7源码网站_源码论坛前言最近想着搭建一个API测试平台,基础的注册登录功能已经完成,就差测试框架的选型,最后还是选择了httprunner,github上已经有很多开源的httprunner测试平台,但是看了下都是基于

  • XML指南——XML 屬性

    XML指南——XML 屬性

发表回复

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

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