递归(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🤣

递归(1)汉诺塔》有46个想法

  1. watch说:

    Oh my goodness! Impressive article dude! Thanks, However I am encountering issues with your RSS. I don’t know the reason why I am unable to join it. Is there anyone else getting similar RSS problems? Anybody who knows the solution will you kindly respond? Thanx!!

  2. resurge supplement review说:

    You’re so cool! I don’t believe I’ve read through anything like this before. So wonderful to find someone with unique thoughts on this topic. Really.. thank you for starting this up. This site is one thing that is required on the web, someone with a bit of originality!

  3. Online Pharmacy说:

    Leading Online Pharmacy – Contact us at +1 (917) 259-3352 for unbelievable rates, discount and offers on any medicine. Get it delivered free of cost at your door steps, call us today. Phone : +1 (917) 259-3352

  4. make money online说:

    This is the right webpage for everyone who wishes to understand this topic. You realize so much its almost hard to argue with you (not that I personally would want to…HaHa). You certainly put a new spin on a topic that has been discussed for a long time. Great stuff, just great!

  5. india visa application说:

    A motivating discussion is definitely worth comment. There’s no doubt that that you should publish more on this issue, it may not be a taboo subject but generally people don’t discuss these subjects. To the next! All the best!!

  6. cbd vape juice说:

    I’m the business owner of JustCBD company (justcbdstore.com) and I am currently seeking to broaden my wholesale side of company. I really hope that someone at targetdomain give me some advice . I thought that the very best way to do this would be to talk to vape companies and cbd stores. I was hoping if someone could recommend a qualified web site where I can buy CBD Shops B2B Sales Leads I am presently looking at creativebeartech.com, theeliquidboutique.co.uk and wowitloveithaveit.com. Not sure which one would be the very best selection and would appreciate any advice on this. Or would it be easier for me to scrape my own leads? Suggestions?

  7. ebiz说:

    Can I simply just say what a comfort to uncover an individual who genuinely understands what they’re talking about over the internet. You certainly understand how to bring an issue to light and make it important. More people ought to check this out and understand this side of the story. I was surprised you aren’t more popular since you surely have the gift.

  8. UI Design Agency说:

    After looking over a number of the blog posts on your web page, I honestly appreciate your way of blogging. I added it to my bookmark webpage list and will be checking back soon. Please check out my web site too and let me know your opinion.

  9. Fayetteville Junk Removal说:

    Hmm it seems like your blog ate my first comment (it was super long) so I guess I’ll just sum it up what I submitted and say, I’m thoroughly enjoying your blog. I too am an aspiring blog writer but I’m still new to everything. Do you have any helpful hints for inexperienced blog writers? I’d really appreciate it.|

  10. Digital Marketing说:

    An outstanding share! I have just forwarded this onto a colleague who had been doing a little research on this. And he actually bought me dinner simply because I found it for him… lol. So allow me to reword this…. Thanks for the meal!! But yeah, thanx for spending some time to discuss this subject here on your blog.

  11. part time cleaner说:

    I do believe all of the concepts you have presented in your post. They’re really convincing and will certainly work. Nonetheless, the posts are very short for novices. May you please extend them a little from next time? Thank you for the post.|

  12. goxapp说:

    After going over a few of the blog posts on your blog, I really appreciate your way of blogging. I added it to my bookmark webpage list and will be checking back in the near future. Please check out my web site as well and tell me what you think.

  13. Reverse Phone Lookup说:

    It is perfect time to make some plans for the future and it is time to be happy. I’ve read this post and if I may just I wish to counsel you few interesting issues or advice. Maybe you could write subsequent articles relating to this article. I wish to read even more things about it!|

发表评论

邮箱地址不会被公开。 必填项已用*标注