【算法图解】递归+调用栈
文章目录

这个盒子里有盒子,而盒子里的盒子又有盒子。钥匙就在某个盒子中。为找到钥匙,你将使 用什么算法?先想想这个问题,再接着往下看。
下面是一种方法。
- 第一种方法使用的是while循环:只要盒子堆不空,就从中 取一个盒子,并在其中仔细查找。
下面是另一种方法:

- 第二种方法使用递归——函数调用自己
基线条件和递归条件:
- 编写递归函数时,必须告诉它何时停止递归。正因为如此,每个递归函数都有两部分:基线 条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己,而基线条件则 指的是函数不再调用自己,从而避免形成无限循环。
栈:
计算机在内部使用被称为调用栈的栈。我们来看看计算机是如何使用调用栈的。


使用栈虽然很方便,但是也要付出代价:存储详尽的信息可能占用大量的内存。每个函数调 用都要占用一定的内存,如果栈很高,就意味着计算机存储了大量函数调用的信息。在这种情况 下,你有两种选择。
- 重新编写代码,转而使用循环。
- 使用尾递归。这是一个高级递归主题,不在本书的讨论范围内。另外,并非所有的语言都支持尾递归。

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论