|

以 fChart 馭 Python: 遞迴函數

   
作者:Ted Lee

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

因為這類的大問題是由其相同型式(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 所示。

本文為會員限定文章

立即加入會員! 全站文章無限看~

                               

已經是會員? 按此登入

只需不到短短一分鐘...

輸入您的信箱與ID註冊即可享有一切福利!

會員福利
1

免費電子報

2

會員搶先看

3

主題訂閱

4

好文收藏

Ted Lee

Author: Ted Lee

從工程師轉任中學教師,又為了捍衛教育理念,投身成為 STEAM 教育工作者,自稱「無可救藥的人文教育理想主義者」的李俊德(Ted Lee)。

Share This Post On

Submit a Comment

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *