寫程式有感2

熟識我的朋友,都會知道我寫電腦程式很爛,這兒我在「寫程式有感」一文中亦提過。

最近的兩篇文章「以幾何法求圓周率的近似值」和「以定積分求圓周率的近似值」我都有自行寫程式來計算有關結果。過程中,我發現 Python 的 function 是可以做 recursion 的。究竟是甚麼?就是類似數學的遞歸數列 (recursive sequence)。

例如我作如下定義:
初始條件:F(1)=1, F(2)=1
遞歸條件:F(n+2)=F(n)+F(n+1)

我們便能求出新的值 F(3),再把 F(2) 和 F(3) 代入遞歸條件,求得 F(4),再把 F(3) 和 F(4) 代入,求得 F(5),如此類推。

這個就是有名的 Fibonacci sequence,亦是本網站首頁所提及的數列,亦都是本網站網名11235813的來源。

心水清的讀者或許知道 Fibonacci sequence 是有通解,無需運用遞歸。我這而只是作為一個例子吧了。

我們人腦可以懂得詮釋以上遞歸數列的定義,哈哈,都說過我寫程式寫得爛,以前真的不知道程式的 compiler/interpreter 亦能明白當中的意義。那也合理,這些都是人腦所設計出來,醒目的人腦自能設計出醒目的 compiler/interpreter 吧?

例如以下程式碼是用 python 3 建立一個函數計算 fibonacci sequence

def fibonacci(n):
    if n==1: return 1
    elif n==2: return 1
    else: return fibonacci(n-1)+fibonacci(n-2)

我以前以為,寫程式時定義一個函數,當中內裏的 function call 必先全部有所定義。但上述最底一行,需要用到 fibonacci(),fibonacci()內用到 finbonacci(),實在好用。

但是這技巧,我上網看人家寫的 code 很少用到,通常人家也用 iteration (如 For loop, While loop) 去做。

這個 fibonacci() 的例子較為簡單,但如果是聯立的 recursive problem,會更顯出其優越:
例如
a(n+1)=f(a(n), b(n), …)
b(n+1)=g(a(n), b(n), …)
.
.
.

這等聯立的問題,以recursion 去構作,只是多幾個 function 罷了,當中的運作由 compiler/interpreter 去處理。但我們化為 iteration 的話,會複雜得多呢!

有人說,這樣做的可讀性很低。不過我覺得可讀性因人而異,對我這個略懂運用數學語言的人來說,recursion 的可讀性實在比 iteration 高得多呢!

自己確實去寫一些 code 去 run 一下,我就發現最少兩個問題。

第一,stack overthrow。拿以上 fibonacci sequence 的例子,當 n 很大時,便會出現此 名為 stack overthrow 的 error。上網搜尋一下,原來用 recursion 的時候,當中的運算不斷累積,佔用很大記憶體。
例如計算 fibonacci(6),compiler/interpreter 會這樣:
fibonacci(6)
=fibonacci(5)+fibonacci(4)
=(fibonacci(4)+fibonacci(3))+(fibonacci(3)+fibonacci(2))
=((fibonacci(3)+fibonacci(2))+(fibonacci(2)+fibonacci(1)))+((fibonacci(2)+fibonacci(1))+1)
.
.
.

如果n是很大的話,要儲存當中的步驟的所需記憶超出系統負荷,便會出現 stack overflow。

第二,運算速度慢。如上例,電腦要一次過運算當中那複雜運算,當然會較費時。只要 n 略大,運算速度可能慢過我用紙筆……

改為 while loop,程式明顯快得多,因為每一步都用一個variable 暫存,逐小去運算吧。

如果有人設計出一個聰明的compiler,把 recursion 看成 iteration,那就太好。既不失對(部分)程式設計員的 readability,亦保持高效能。問了一下朋友,原來部分 compiler 對 "tail recursion" 是有這類優化,但暫時普遍的 recursion 還未做到。

不過我覺得把 recursion 化為 tail recursion,實在不自然,對我來說大大失卻了原有的可讀性。

Anyway,這次經驗,更體驗到學習的過程很多時都要經過嘗試才有所得著。在此勉勵各位學習者要勇於嘗試新事物。

如果小時候有一些令我感興趣的東西去勾起我學習寫程式的意欲,多加嘗試,可能現在我寫程式會好些少,可以靠寫 code 呃兩餐飯仔吧,哈哈哈。人大了出來工作,實在少了精力去鑽研。


Add a New Comment
or Sign in as Wikidot user
(will not be published)
- +