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

全栈程序员站长

发布于 2022-11-07 17:18:02

5040

发布于 2022-11-07 17:18:02

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

递归章节

一.什么是递归

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

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 问题求解方法是递归的

如，汉罗塔问题：

首先定义函数：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的阶乘分解和求解过程

递归模型的一般步骤：

（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）反过来啦，请读者自行体会：