一.简介
在哔哩哔哩看视频学的,赫斌老师数据结构入门的内容-b站搜索:av6159200(P50-P58),因为我在早期学c语言的时候就学过的递归,那时一直理解不了汉诺塔,最后花了很长时间才彻底搞懂,在看到学到这个数据结构有递归的时候,自己就重新写了一下汉诺塔递归的实现,不过通过了视频了解了大致递归的一下原理把.
二.什么是递归
递归其实说得简单点,大概就是自己调用自己,或者调用别的函数,并且递归要有结束条件,就是当条件是什么的时候,就结束调用,
简单的举例:
累加:1+2+3+4,为了简单的理解就不加到100了
利用递归的话,我们就可以用4进去一直来减1,然后当减到为1的时候结束调用.
int add(n)
{
if(n==1) //为1的时候结束调用
{
return 1;
}
else
{
return = n+ add(n-1); //一直调用自己
}
}
n = 4时 即 return = 4 + add(3)
n = 3时 即 return = 3 + add(2)
n = 2 时 即 return = 2 + add(1)
然后我们又知道n为1 时 返回的是1
所以反向推就可以知道 add(2) = 2 + 1
add(3) = 3 + 2 + 1
add(4) = 4 + 3 + 2 +1
这其实类似于栈的原理-先进后出,就是每次要用最后一个来推出上面的那一个.
三.递归实现汉诺塔的图解
汉诺塔的来历,相信很多人都知道了,这里就不多说了.
四.汉诺塔源码(可复现)
# include <stdio.h>
void hanoi(char , char , char, int); //函数声明
int main(void)
{
int val;
printf("请输入你要移动几个盘子\n");
printf("盘子 = ");
scanf("%d", &val);
hanoi('A' , 'B' , 'C', val);
return 0;
}
/* 汉诺塔 */
void hanoi(char A, char B, char C, int val)
{
if(1 == val)
{
printf("%c->%c\n", A, C);
}
else
{
hanoi(A, C, B, val-1);
printf("%c->%c\n", A, C);
hanoi(B, A, C, val-1);
}
}
五.递归的应用
树和森林就是以递归的方式定义的
树和图的很多算法都是以递归来实现的
很多数学公式就是以递归的方式定义的(如:斐波拉契序列)
六.循环和递归
递归:
易于理解
速度慢
所用存储空间大
循环:
不易理解
速度快
所用存储空间小
