第1章 遞迴:老和尚與小和尚的故事
一天回家,趙律師拉著商老師問東問西,問了半天大數據和AI的問題。商老師有點好奇,因為他知道趙律師是出了名的不喜歡數學和邏輯。趙律師說周圍的朋友們都在學習程式碼,表示自己也要學習,建議商老師開一個家庭課堂。
商老師覺得教了這麼多年的學生,開一個家庭課堂還不是手到擒來?於是當晚打算從最基礎的遞迴開始講起。商老師從函數、定義、函數呼叫開始解釋,但是說了好幾回,趙律師還是未能理解。商老師越說越快,逐漸失去耐心了。
1.1 「老和尚與小和尚的故事」中的遞迴
看著對面趙律師越來越陰沉的臉色,商老師心裡暗暗叫苦:這該怎麼辦?萬一教不好,就要影響家庭和諧了。」這時趙律師說:「其實你講了這麼多,聽起來很像小時候聽過的一個故事(如圖1-1所示)。」
從前有座山,山裡有座廟,
廟裡有一個老和尚和一個小和尚,
老和尚講故事給小和尚聽,故事講的是:
從前有座山,山裡有座廟,
廟裡有一個老和尚和一個小和尚,
老和尚講故事給小和尚聽,故事講的是:
……
商老師一拍大腿,這就對了!這簡單的故事其實蘊含了電腦科學裡重要的遞迴(Recursion)思想。
要講清楚這個故事的遞迴概念,需要先簡單地了解幾個相關概念。為了便於理解,這裡用自然語言和程式語言結合的虛擬碼來描述。虛擬碼是機器不能執行的語言,但是便於人們理解演算法的運算過程。
首先,我們需要理解電腦程式碼裡的函數。我們可以從數學中的函數開始理解。函數代表的是輸入和輸出的關係。在數學課本上,常見的函數經常表示為f(x),代表著輸入參數x後得到f(x)的值,f(x)是一個人為定義的運算過程。電腦程式碼裡的函數則用程式語言來描述這個運算過程。我們以函數在運算過程中是否使用該函數本身為分類標準,可以將函數分為遞迴函數和非遞迴函數。
										一天回家,趙律師拉著商老師問東問西,問了半天大數據和AI的問題。商老師有點好奇,因為他知道趙律師是出了名的不喜歡數學和邏輯。趙律師說周圍的朋友們都在學習程式碼,表示自己也要學習,建議商老師開一個家庭課堂。
商老師覺得教了這麼多年的學生,開一個家庭課堂還不是手到擒來?於是當晚打算從最基礎的遞迴開始講起。商老師從函數、定義、函數呼叫開始解釋,但是說了好幾回,趙律師還是未能理解。商老師越說越快,逐漸失去耐心了。
1.1 「老和尚與小和尚的故事」中的遞迴
看著對面趙律師越來越陰沉的臉色,商老師心裡暗暗叫苦:這該怎麼辦?萬一教不好,就要影響家庭和諧了。」這時趙律師說:「其實你講了這麼多,聽起來很像小時候聽過的一個故事(如圖1-1所示)。」
從前有座山,山裡有座廟,
廟裡有一個老和尚和一個小和尚,
老和尚講故事給小和尚聽,故事講的是:
從前有座山,山裡有座廟,
廟裡有一個老和尚和一個小和尚,
老和尚講故事給小和尚聽,故事講的是:
……
商老師一拍大腿,這就對了!這簡單的故事其實蘊含了電腦科學裡重要的遞迴(Recursion)思想。
要講清楚這個故事的遞迴概念,需要先簡單地了解幾個相關概念。為了便於理解,這裡用自然語言和程式語言結合的虛擬碼來描述。虛擬碼是機器不能執行的語言,但是便於人們理解演算法的運算過程。
首先,我們需要理解電腦程式碼裡的函數。我們可以從數學中的函數開始理解。函數代表的是輸入和輸出的關係。在數學課本上,常見的函數經常表示為f(x),代表著輸入參數x後得到f(x)的值,f(x)是一個人為定義的運算過程。電腦程式碼裡的函數則用程式語言來描述這個運算過程。我們以函數在運算過程中是否使用該函數本身為分類標準,可以將函數分為遞迴函數和非遞迴函數。