遞歸系統堆棧的狀態

Question

enter image description here

有人可以解釋什麼是系統堆棧的狀態？以及它如何連接到二分查找？

Answer 1

顯然的問題是關於兩個不同的東西，即

1. 二進制搜索，可重複二者並遞歸執行;
2. 關於調用堆棧的遞歸和迭代實現之間的差異。

二進制搜索是指在排序列表（或排序數組）中查找對象。策略是檢查列表中間的對象;要麼找到想要的對象，要麼沒有。如果找不到，則必須在列表的左半部分或右半部分進行搜索;無關的一半可以被丟棄。

這種方法可以迭代實現，其中輔助索引控制搜索。或者，它可以遞歸地實現，其中二分搜索相關的一半再次被調用。

在迭代實現中，對二進制搜索只有一個調用，這意味着不會爲搜索生成新的堆棧幀。在遞歸實現中，爲每個遞歸調用生成一個新的棧幀。由於每個步驟都會丟棄至少一半的搜索空間，這意味着最多可生成log(n)新的堆棧幀（每次遞歸調用一個），其中n是初始列表中的對象數。

Answer 2

SHORT：基本上，堆棧是系統用來在調用它時存儲函數狀態的一部分內存（參數，變量等）。對於更長的描述，你可以參考這個偉大的link。二進制搜索沒有連接到堆棧，實際上，任何一段代碼都可以使用堆棧。在你的情況下，你被要求的是當你調用你的二進制搜索功能時，描述堆棧的狀態（如你提供的圖片中的那個）。