递归系统堆栈的状态

Question

enter image description here

有人可以解释什么是系统堆栈的状态？以及它如何连接到二分查找？

Answer 1

显然的问题是关于两个不同的东西，即

1. 二进制搜索，可重复二者并递归执行;
2. 关于调用堆栈的递归和迭代实现之间的差异。

二进制搜索是指在排序列表（或排序数组）中查找对象。策略是检查列表中间的对象;要么找到想要的对象，要么没有。如果找不到，则必须在列表的左半部分或右半部分进行搜索;无关的一半可以被丢弃。

这种方法可以迭代实现，其中辅助索引控制搜索。或者，它可以递归地实现，其中二分搜索相关的一半再次被调用。

在迭代实现中，对二进制搜索只有一个调用，这意味着不会为搜索生成新的堆栈帧。在递归实现中，为每个递归调用生成一个新的栈帧。由于每个步骤都会丢弃至少一半的搜索空间，这意味着最多可生成log(n)新的堆栈帧（每次递归调用一个），其中n是初始列表中的对象数。

Answer 2

SHORT：基本上，堆栈是系统用来在调用它时存储函数状态的一部分内存（参数，变量等）。对于更长的描述，你可以参考这个伟大的link。二进制搜索没有连接到堆栈，实际上，任何一段代码都可以使用堆栈。在你的情况下，你被要求的是当你调用你的二进制搜索功能时，描述堆栈的状态（如你提供的图片中的那个）。