以 fChart 馭 Python： 遞迴函數

Posted By Ted Lee on 1 月 4, 2023 in python, 教學文, 程式教育 | 0 comments

遞迴是程式自己呼叫自己的一種抽絲剝繭的解題計巧。

因為這類的大問題是由其相同型式（pattern）的小問題所疊代（iterate）而增長而成的。所以，當問題空間（problem space）降低至易於處理的小大（size）時，我們就很容易從小問題的答案再往上一層一層回溯（backtrack）而組合出原大問題的解答。

例如：欲求數列（sequence） 1, 1, 2, 3, 5, ... 的第 10 項為何數字，我們可以發現，這串數列好像有一個隱含的規律（implicit regularity）是：第 i 項是前兩項 (i-2), (i-1) 的和，當 i > 2 時。例如：5 = 3 + 2。

在表 1 的「10 大項目之 10」的 4 個實例（可從此處下載）中將探討電腦科學（Computer Science，CS）中這類的經典（classical）遞迴問題──將大問題拆解（divide）為小問題，再將小問題的答案逐步組合（combine）為大問題的解答。

前題：大問題和小問題具有相同的結構性（structure）！

表 1：10 大項目之 10

遞迴分析

在本小節中，我們甞試使用運算思維（computational thinking）的法則來分析費式數列問題：

步驟 1：拆解（decomposition）。我們設計了表 2 的費氏數列空白觀察表（observation table）來推敲此數列的生成（generate）過程。其結果如表 3 所示。