【算法图解】递归+调用栈

截屏2022-03-02 下午9.52.45

这个盒子里有盒子,而盒子里的盒子又有盒子。钥匙就在某个盒子中。为找到钥匙,你将使 用什么算法?先想想这个问题,再接着往下看。

下面是一种方法。截屏2022-03-02 下午9.53.12

  • 第一种方法使用的是while循环:只要盒子堆不空,就从中 取一个盒子,并在其中仔细查找。

下面是另一种方法:

截屏2022-03-02 下午9.53.58

  • 第二种方法使用递归——函数调用自己

基线条件和递归条件:

  • 编写递归函数时,必须告诉它何时停止递归。正因为如此,每个递归函数都有两部分:基线 条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己,而基线条件则 指的是函数不再调用自己,从而避免形成无限循环。

栈:

计算机在内部使用被称为调用栈的栈。我们来看看计算机是如何使用调用栈的。截屏2022-03-02 下午9.56.47

截屏2022-03-02 下午9.57.31

截屏2022-03-02 下午9.57.52

使用栈虽然很方便,但是也要付出代价:存储详尽的信息可能占用大量的内存。每个函数调 用都要占用一定的内存,如果栈很高,就意味着计算机存储了大量函数调用的信息。在这种情况 下,你有两种选择。

  • 重新编写代码,转而使用循环。
  • 使用尾递归。这是一个高级递归主题,不在本书的讨论范围内。另外,并非所有的语言都支持尾递归。

评论

暂无评论