递归(1)汉诺塔

递归是什么

递归就是自己调用自己,我们再来看看函数调用是怎么回事

     当一个函数在运行期间调用另一个函数,运行在被调用函数之前系统需要将被调函数所有的参数,返回地址等传递给被调函数,为被调函数在内存中分配空间,同时将控制转移到被调函数入口
从被调函数返回主函数之前,系统要保存被调函数的返回结果,释放被调函数所占的内存空间,依照地址返回调用函数继续执行、

     当有多个函数互相调用时,如a函数调用了b,b又调用了c,按照后调用先执行的原则,实际上就是栈结构,最后调用的函数处于栈顶,每调用一个函数,就在栈顶分配一块内存空间,每当一个函数执行完毕就会进行出栈操作释放空间,而递归最常出现的问题就是爆栈和超时,著名的StackOverflow.com也是由此而来。

其实对于计算机来说,a调用b 和 a调用a并没有什么不同

递归必须要满足的三个条件

1.递归必须有明确的终止条件,且一定在某一时刻可以满足该条件
2.该函数所处理的数据规模在递减(递归的思想是把问题分解成为规模更小且与原问题有着相同解法的问题
3.这个转化必须是可解的(其实有好多时候,这个问题能不能用递归,该怎么用是个数学问题)

汉诺塔

  • 直接来看一下汉诺塔的伪算法
//
if(n > 1)
{
   将n-1个盘子借助C移动到B
   将第n个盘子移动到C
   将n-1个盘子借助A移动到C
}
  • 上代码
    //
    void fun(int n,char a,char b,char c)
    {
        if(n == 1)
        {
            printf("把第%d个盘子从%c移到%c\n",n,a,c);
        }
        else{
            fun(n-1,a,c,b);
            printf("把第%d个盘子从%c移到%c\n",n,a,c);
            fun(n-1,b,a,c);
        }
    }
    
    int main()
    {
        fun(3,'a','b','c');
        return 0;
    }
    /*输出
    把第1个盘子从a移到c
    把第2个盘子从a移到b
    把第1个盘子从c移到b
    把第3个盘子从a移到c
    把第1个盘子从b移到a
    把第2个盘子从b移到c
    把第1个盘子从a移到c
    */

    唯一需要注意就是这个函数的后三个参数,第一个表示的是当前盘子在哪,第二个表示的是用作辅助的柱子,第三个是目标柱子

  • 并没有深入探讨如何优化递归和太多算法的问题,只是简单的用汉诺塔来说明了递归的使用方法,因为有些问题只能用递归来解决,同时在数据结构中将会有大量使用递归的地方另一个用到递归的问题快速排序
  • 有问题欢迎大家提问哦0。0 可以直接评论😂 也可以QQ🤣