设为首页 - 加入收藏 定西香江堵经 (http://www.0932zz.com)- 国内知名站长资讯网站,提供最新最全的站长资讯,创业经验,网站建设等!
热搜: 芯片 唯品 2018
当前位置: 首页 > 运营中心 > 建站资源 > 优化 > 正文

深入理解递归,是你误解了递归

发布时间:2019-09-18 09:44 所属栏目:[优化] 来源:源理君
导读:递归是一个神奇的算法,它是编程书籍中讲解的最尴尬部分。这些书籍通常会展示一个递归的阶乘实现,然后警告你,虽然它能运行但是它非常的慢并且可能会堆栈溢出而崩溃。虽然大家对它持怀疑态度,但是这不影响递归是算法中最强大的想法。 让我们来看看经典的

递归是一个神奇的算法,它是编程书籍中讲解的最尴尬部分。这些书籍通常会展示一个递归的阶乘实现,然后警告你,虽然它能运行但是它非常的慢并且可能会堆栈溢出而崩溃。虽然大家对它持怀疑态度,但是这不影响递归是算法中最强大的想法。

让我们来看看经典的递归阶乘:

factorial.c

  1. #include??
  2. ?
  3. int?factorial(int?n)?
  4. {?
  5. ????????int?previous?=?0xdeadbeef;?
  6. ?
  7. ????????if?(n?==?0?||?n?==?1)?{?
  8. ????????????????return?1;?
  9. ????????}?
  10. ?
  11. ????????previous?=?factorial(n-1);?
  12. ????????return?n?*?previous;?
  13. }?
  14. ?
  15. int?main(int?argc)?
  16. {?
  17. ????????int?answer?=?factorial(5);?
  18. ????????printf("%d\n",?answer);?
  19. }?
  20. ?????

一个函数调用自身的想法起初非常神秘。为了解释整个过程,下图展示了factorial(5)被调用到n == 1 栈上结构。

深入理解递归,是你误解了递归

每次调用factorial都会生成一个新的栈帧。这些栈帧的创建和销毁使得递归因子比其迭代部分慢。在调用开始和返回之前的这些栈帧累积是可能耗尽栈空间并使程序崩溃。

但是这些担忧通常是理论上的。例如,栈帧 factorial每个占用16个字节(这可以根据栈对齐和其他因素而变化)。如果您在计算机上运行现代x86 Linux内核,通常默认有8兆字节的堆栈空间,因此factorial n最多可以处理512,000。这是一个巨大数,需要8,971,833位来表示这个数,所以栈空间是我们问题中最少的:一个微弱的整数 - 甚至是64位 - 在我们用完栈空间之前会溢出数万次。

我们稍后会看一下CPU的使用情况,但是现在让我们从位和字节中退一步,看看递归作为一种通用技术。我们的阶乘算法归结为将整数N,N-1,... 1推入堆栈,然后以相反的顺序将它们相乘。我们使用程序的调用堆栈执行此操作的前提是:我们可以在堆上分配堆栈并使用它。虽然调用堆栈确实具有特殊属性,但它只是您可以使用的另一种数据结构。

一旦你看到调用堆栈作为一个数据结构,其他东西就变得豁然开朗了:将本身之前所有这些整数累加起来再乘以自身这显然不是明智的选择。 使用迭代过程计算阶乘更为明智。

有一个传统的面试问题,在迷宫中放一只老鼠,你帮助老鼠找奶酪,假设老鼠可以在迷宫中向左或向右转。你会如何建模并解决这个问题?

像生活中的大多数问题一样,你可以将这种啮齿动物的任务抽象到一个图形,特别是一个二叉树,其中节点代表迷宫中的位置。然后你可以尽可能地让老鼠左转,当它到达死胡同时回溯然后右转。下图就是老鼠路径 :

深入理解递归,是你误解了递归

每条边(线)都可以左转或右转,老鼠可以选择。如果任一转弯被阻止,则相应的边缘不存在。无论您使用调用堆栈还是其他数据结构,此过程本质上都是递归的。但使用调用栈非常简单:

Maze.c

  1. #include??
  2. #include?"maze.h"?
  3. ?
  4. int?explore(maze_t?*node)?
  5. {?
  6. ??int?found?=?0;?
  7. ?
  8. ????if?(node?==?NULL)?{?
  9. ????????return?0;?
  10. ????}?
  11. ?
  12. ????if?(node->hasCheese)?{?
  13. ????????return?1;?//?found?cheese?
  14. ????}?
  15. ?
  16. ??found?=?explore(node->left)?||?explore(node->right);?
  17. ??return?found;?
  18. }?
  19. ?
  20. int?main(int?argc)?
  21. {?
  22. ????????int?found?=?explore(&maze);?
  23. }?

在maze.c:13中找到奶酪,下图是堆栈。

深入理解递归,是你误解了递归

虽然这里很难摆脱递归,但这并不意味着它必须通过调用栈来完成。例如,你可以使用一个字符串 RRLL来跟踪转弯,并依靠字符串来决定鼠标的下一步行动。或者你可以分配其他变量来记录奶酪寻找的状态。你仍然在实现递归过程,但滚动你自己的数据结构。

【免责声明】本站内容转载自互联网,其相关言论仅代表作者个人观点绝非权威,不代表本站立场。如您发现内容存在版权问题,请提交相关链接至邮箱:bqsm@foxmail.com,我们将及时予以处理。

网友评论
推荐文章