計算機科學基礎/抽象和遞迴
只要程式很小，程式設計就很容易。不可避免地，隨著我們建立的程式來解決日益複雜的問題，我們的程式會變得越來越大。我們用來使演算法和程式保持簡單的技巧之一是抽象，這是一個在藝術、數學和工程等許多領域廣泛使用的概念。在本章中，我們將研究如何將這種技術應用於演算法設計和程式設計。
抽象去除細節，幫助我們集中注意力。例如，汽車為駕駛員提供了一組簡單的控制作為介面。只要我們知道如何使用介面，我們就可以駕駛汽車，而無需瞭解它的內部工作原理。汽車的內部工作原理對於駕駛員來說是不必要的細節，除非他們是賽車手，他們需要這種知識才能最有效地駕駛汽車。這種介面自第一輛汽車問世以來就沒有太大的變化。抽象還透過從具體例子中提取共同特徵來概括概念。這種汽車介面從各種汽車中提取了共同的汽車特徵（駕駛員需要了解的駕駛汽車的資訊）。一旦你學會了駕駛一輛汽車，你也就學會了駕駛所有同類型的汽車。這是一個強大的想法。這種抽象還使汽車製造商能夠自由地改變汽車的內部設計，而不會影響使用者。
我們已經瞭解到，演算法設計是使用計算解決問題和程式設計的第一步。最難的部分不是程式設計/編碼，而是跟蹤大型程式中的細節。為了使我們的程式保持“小”，主要有兩種方法：分塊和分層，這是抽象的兩種隱喻。分塊將功能分解成更小的單元，並讓單元透過定義良好的介面相互互動。例如，在 Snap! 中，你可以將演算法實現為一個塊，然後只要你能根據介面呼叫塊，並使用正確的引數序列，你就可以在指令碼中的任何地方使用它。分層將功能單元（塊）分離成不同的層，以分離關注點並簡化互動模式，使複雜性更容易管理。下圖說明了分層的想法。
透過將功能單元（塊）組織成層，我們可以簡化互動並允許對層進行併發開發。
在圖中，每一層都依賴於它下面的層才能發揮作用，併為它上面的層提供服務。例如，第一層中的一個單元只允許呼叫它下面的第二層中的單元。所有互動都限制在彼此相鄰的層對之間，在一個層堆疊中。我們可以用新的實現完全替換一個層，而不會影響堆疊的其餘部分，這實現了模組化。相反，如果允許任何任意互動，我們最終可能會得到緊密耦合的系統，如下圖所示。
沒有任何限制，任何單元（塊）都可以呼叫任何其他單元。
使用抽象來實現簡化和泛化確實是一個強大的組織理念。回想一下第一章中的思維實驗，我們構建了一臺可以解決方程組的機器。這臺機器是透過抽象構建的——我們使用更小的（更基本的）構建塊來構建更大的構建塊，並將每個塊作為一個單元來處理，而忽略內部細節。
Snap! 環境允許我們以類似的方式構建程式。當定義一個塊時，它就成為一個新的構建塊（使用者定義的）。該塊可以任意複雜，但要使用它，我們只需要瞭解它的介面——它的名稱和它的引數列表。不必要的細節對使用者隱藏，極大地簡化了程式設計所涉及的思考過程。
讓我們來看一個具體的例子。為了建立一個精靈來繪製不同的等邊形狀，我們可以為繪製每種形狀（如三角形、正方形、五邊形等）建立一個塊。Snap! 中的塊是一個抽象，它隱藏了細節，代表了某種行為/意圖。以下塊繪製了一個特定大小的正方形。
這個 Snap! 塊繪製了一個特定大小的正方形。
為了繪製三角形，我們可以使用類似的邏輯結構。
這個 Snap! 塊繪製了一個等邊三角形。
繪製三角形塊重複三次，每次繪製一個邊，並旋轉 120 度。你知道為什麼精靈必須旋轉 120 度才能在兩條邊之間形成 60 度角嗎？我希望你已經注意到，相同的邏輯結構可以用來建立塊來繪製任何等邊形狀。與其為每個形狀建立一個塊，我們可以將任務泛化成一個可以繪製任何形狀的塊。此塊需要一個額外的資訊——邊的數量。
這個 Snap! 塊可以繪製任何等邊形狀。
有了邊的數量，我們就可以確定形狀的內角，這就是我們繪製形狀所需的一切。如果你不確定如何使用邊的數量來計算內角，請檢視這個資源。這個塊可以作為繪製等邊形狀（多邊形）任務的抽象。你可能已經注意到邊的長度是硬編碼的（作為常量輸入，而不是引數）。如果我們想繪製不同大小的形狀怎麼辦？我們可以透過新增另一個引數來進一步泛化塊的功能，並使用它來控制邊的長度。
這個 Snap! 塊可以繪製任何大小的等邊多邊形。
透過這個例子，我們已經演示瞭如何定義塊以抽象掉任務的細節，並泛化解決方案以解決更多問題。
遞迴是一種自相似的模式——整體由結構上類似於整體的較小部分組成。例如，樹由看起來像小樹的樹枝組成。類似地，計算機上檔案系統的目錄樹和家譜的家譜樹也表現出類似的模式。下圖顯示了一棵遞迴樹。
使用 Logo 程式語言建立的樹，大量依賴遞迴。
自相似性使我們能夠以更簡潔、更優雅的方式定義表現出這種模式的概念。樹可以是隻有一根樹幹沒有分支，也可以是一根樹幹上有許多分支，而每個分支都是一棵樹。這個定義涵蓋了所有可能的樹結構。你如何描述下圖？
-
一種稱為 Droste 效應的遞迴視覺形式。這幅圖中的女人手裡拿著一件物體，物體中包含著她拿著一件相同物體的較小影像，而物體中又包含著她拿著一件相同物體的更小影像，依此類推。
如果你要透過反覆深入到更細的細節來實現，它永遠不會結束。你能遞迴地定義這幅圖嗎？另一個例子是數學中階乘函式的定義： 並且對於所有 這個遞迴定義不僅定義了階乘，而且還描述了一種計算階乘的方法。例如，5! 可以從 4! 計算出來，4! 等於 4 乘以 3!，3! 等於 3 乘以 2!，2! 等於 2 乘以 1!，1! 根據定義等於 1。
如果我們解決的問題是自相似的——解決整個問題就是解決與整體相似的部分——那麼我們為整體定義的解決方案就可以用於解決子問題（遞迴）。遞迴解決方案的妙處在於問題的定義就是解決方案，如階乘示例所示。為了設計遞迴解決方案，我們進行“美好願望式”思考——當我們描述對整個問題的解決方案時，我們希望它已完全定義，可以用於解決較小的子問題。在計算機程式設計中，這被稱為遞迴式思考/程式設計。為了進行遞迴程式設計，我們將問題的解決方案描述為一個函式/過程/塊，在這個函式中，我們將較大的問題分解成較小的問題，並使用我們正在定義的函式來解決較小的問題。如果問題是有限的，最終較小的問題會變得非常簡單，可以直接解決。在這種情況下，遞迴就會停止。我們稱這些情況為基本情況。當我們的程式到達所有基本情況時，我們就已經解決了整個問題，因為所有子問題都已解決，包括我們開始時的問題。在任何遞迴函式中，必須存在兩個基本部分：基本情況和遞迴情況。遞迴情況部分將較大的問題分解成較小的部分。基本情況透過解決可以直接解決的問題來停止遞迴。如果這兩個部分都存在並且結構合理，該演算法（函式）就可以透過要求自身的克隆來解決部分問題來解決任何大小的問題。遞迴式問題解決是一個強大的理念，因為它簡化了我們的思考方式：如果你能遞迴地定義一個問題，你就可以遞迴地解決它。遞迴解決方案更加優雅，也更容易驗證，但它只適用於可以遞迴定義的問題。
在我們研究一些具體的例子之前，我們將介紹函式的概念，它使遞迴解決方案更容易管理。Snap! 中的一個塊如果具有以下屬性，則被視為函式（類似於數學函式）
- 一個函式接受任意數量的輸入（零個或多個）
- 一個函式始終返回/報告一個結果值
- 對於相同的輸入，函式始終報告相同的結果值
- 函式的執行不會對環境產生副作用
在這樣的限制下，Snap! 中的函式是獨立執行任務（在它自己的世界中）並傳遞結果以供進一步處理的塊。根據這個定義，以下列表中的哪些塊是函式？
此列表中的一些塊是函式。
考慮二分查詢演算法
Find an item (target) in a sorted list if the list is empty, the target cannot be found consider the item in the middle, if it matches the target you are done otherwise, decide which half to search next
搜尋有序列表的一半僅僅是整個問題的較小版本/部分，所以我們可以應用相同的演算法，希望該演算法已完全定義。這個過程會一直持續，直到列表為空或找到搜尋目標。
顯然基本情況是
- 如果列表為空，則找不到目標
- 如果目標位於列表中間，則找到目標
遞迴情況是（假設列表按升序排序）
- 如果列表中間的專案小於搜尋目標，則繼續搜尋列表的後半部分
- 否則，繼續搜尋列表的前半部分