計算機科學基礎/遞迴再探

遞迴再探

遞迴解法提供了另一種強大的方法來解決自相似問題。我們將要研究的例子是二分查詢解法。

二分查詢如何工作？

在排序列表中識別目標專案的過程。首先是基本情況，直接判斷中間專案是否等於目標。如果中間專案等於目標，則搜尋完成，並報告索引。如果列表為空，則搜尋報告 -1 或未找到。否則，判斷目標是大於還是小於中間專案，以決定搜尋列表的哪一半。

接下來，如果中間專案大於目標，則搜尋列表的前一半，否則，我們搜尋列表的後一半。這與我們最初開始時遇到的問題相同，使其成為一個遞迴或自相似問題。

下圖是二分查詢程式碼實現。基本情況和遞迴情況已標出。

二分查詢用於在排序列表中查詢專案（目標）。它由組成遞迴解法的基本情況和遞迴情況組成。

二分查詢：抽象簡化

簡化二分查詢解法的一個好方法是使用抽象。之前顯示的影像使用了一個名為“中間位置”的輔助塊，該塊用於在給定排序列表的第一個和最後一個索引時找到中間索引（見下文）。

二分查詢中用於在給定輸入的第一個和最後一個索引之間找到中間索引的輔助塊。

簡化二分查詢解法的另一種方法是增加另一個抽象層。下面的輔助塊顯示了目標和列表作為輸入傳遞到“二分查詢”塊中（見下文）。當遞迴搜尋塊檢測到排序列表的第一個和最後一個索引時，實際的遞迴解法得以實現。“二分查詢”塊允許使用者呼叫遞迴搜尋，而無需使用者提供第一個和最後一個索引。使用者只看到開始二分查詢所需的資訊和/或塊。使用者將不會看到遞迴搜尋或解決方案背後的幕後過程。

二分查詢輔助塊，增加了另一個抽象層，透過呼叫遞迴搜尋塊來搜尋列表中的目標。

二分查詢：跟蹤

我們之前討論過使用“二分查詢”簡化遞迴搜尋的介面，它將目標和列表作為輸入（見下例）。然後，呼叫“遞迴查詢”，並且立即解決第一個基本情況，因為我們的目標 9 不等於 5。由於目標 9 大於 5（中間索引處的元素），我們搜尋列表的後一半（索引 4 到索引 5）。重複該過程，並拆分列表，檢查位置和/或索引 4 處的第一個元素。目標大於 7，再次重複遞迴搜尋，再次搜尋列表的後一半。基本情況 2 立即解決，目標 9 等於列表中的 9；它位於中間索引 5 處。

現在，由於在索引 5 處找到了目標，遞迴搜尋報告回第二個遞迴搜尋，而第二個遞迴搜尋又報告回第一個遞迴搜尋。最後，索引 5 被報告回“二分查詢”塊的頂層使用者。

此影像顯示了當目標等於 9 時如何跟蹤二分查詢。逐步使用基本情況和遞迴情況進行報告。

如果在列表中沒有找到目標，則二分查詢報告 -1（見下文）。會進行相同的遞迴搜尋呼叫，但在最後一次呼叫時，開始索引大於結束索引，這表明沒有找到目標，並且已到達列表的末尾。

此影像顯示了當目標在排序列表中找不到時如何跟蹤二分查詢。如果列表中沒有目標，則解決方案報告 -1 或未找到。

科赫曲線

1904 年，Helge von Koch 發現了馮·科赫雪花曲線，“一條在分形幾何學研究中很重要的連續曲線”（3）。科赫曲線從一條長度為 1 個單位的單線段開始。然後，用四個新的線段替換該線段，每個線段的長度是原始線段的三分之一，也稱為生成器。該過程無限重複，並生成科赫曲線。下圖顯示了階段 0 到 2 的過程。

這顯示了生成器（階段 0）和科赫曲線的階段 1 和 2 的迭代。

科赫曲線的長度是無限的。該曲線是遞迴的另一個有趣的實現，它是自相似的；曲線不斷複製自身。

科赫雪花

在等邊三角形的三個邊上使用相同的科赫曲線生成器，我們可以看到重複的迭代最終開始看起來像雪花（請參閱 科赫雪花）。雪花具有無限的周長和有限的面積。

檢查科赫雪花的每個階段，都會建立一個關於每邊線段數量、長度和曲線總長度的模式，如下所示。每邊線段的數量是上一個階段的四倍。每次將線段長度分成相等的三個部分，這將給出每個線段的長度。原始階段，等邊三角形，是為什麼我們取每邊線段數量的三倍除以線段長度的 stage 冪次（當前正在實現的階段）。

透過跟蹤不同的迭代，可以看出科赫雪花的模式。

探索問題

研究科赫曲線和雪花圖案已經確立，並顯示瞭如何重複相同的過程來生成每個階段。我們可以使用遞迴過程來解決相同問題的抽象。

• 第 N 次迭代的總長度是多少？檢視數字在簡化之前和之後形成的模式。
• 您期望科赫曲線是什麼樣子的？換句話說，您期望無限次重複此操作會發生什麼？
• 科赫曲線的長度是多少？
• 你能估計每個階段的面積嗎？最終雪花的面積是多少？

回顧之前的題目，我們可以開始觀察科赫曲線和科赫雪花的行為。

1. 根據已建立的模式，很明顯第 N 次迭代的總長度將是 3*(4/3)ⁿ。
2. 由於科赫曲線無限重複，它會開始看起來更平滑，因為線條會看起來越來越近，儘管永遠不會接觸。
3. 科赫曲線的長度是無限的（在將生成器應用無限次之後）。
4. 最終雪花的面積是有界的（有限的）。