我要講的最後一個 big idea 是 recursion 。

例如以下的 maze procedure

to maze
forward 10 right 90
forward 15 right 90
forward 20 right 90
forward 25 right 90
forward 30 right 90
forward 35 right 90
forward 40 right 90
forward 45 right 90
forward 50 right 90
forward 55 right 90
forward 60 right 90
forward 65 right 90
end
clearscreen
maze

會畫出如迷宮般的圖畫。
上次講過的 big idea #1 是找出 pattern 。 ((其實順勢可以講下,有一個 principle 叫做 Don't repeat yourself (DRY) 。你看見以上的 procedure 是有一個不停出現的 forward n right 90 的句語,明顯地我是用 copy and paste 弄出來的。這種不停重覆自己的程式,時常要 copy and paste 的,都不算好程式,原因是如果不停重覆的地方有錯的話,就要全部都改正。故此,最好的方法是找出不停重覆部份 pattern ,例如轉成 procedure 之類。當此 procedure 出現問題,只需要修改此 procedure 的程式碼,而無需通處找。)) 從以上的程式碼,我們見到 forward n right 90 是不停重覆的,而每次 n 都增加 5 。我們可以將 maze 改寫成:

to maze :n
forward :n right 90
end
clearscreen
maze 10

但是這個方法只會行一步。要再行多一步,就要輸入

maze 10 + 5

不如我們試試這樣 ((建議用 papert 的 run it slowly 執行)) :

to maze :n
forward :n right 90
maze : n + 5
end
clearscreen
maze 10

龜是會動,而且會不停的畫迷宮。如果我們不叫停它,它是會不停的畫。這個情況叫做 infinite loop ,俗語叫「 loop 死」。若然用之前講過的 substitution model ,執行 maze 10 到底發生甚麼事?電腦先叫 mabel 執行 maze 10 , mabel 叫龜行前 10 步,轉左,再執行 maze 10 + 5 ,即是 maze 15 。電腦今次叫 macy 執行 maze 15 , macy 叫龜行前 15 步,轉左,再執行 maze 15 + 5 ,即是 maze 20 。電腦今次叫 mary 執行 maze 20 , mary 叫龜行前 20 步.....

有沒有方法叫電腦自行停止呢?有,只要加入一個 if statement ,這個 if statement 表達的是,若然合符某條件, recursion 就要終結。這個東西叫做 base case 。因此,如果我們不想 recursion 沒完沒了,就要加入 base case 。

to maze :n
if :n > 100 [stop]
forward :n right 90
maze :n + 5
end

maze 10

加入了 base case 之後,當 recursion 由 maze 10 執行到 maze 100 ,電腦再叫 miranda 執行 maze 105 時,檢查 :n 是否大於 100 。由於 105 大於 100 ,故此會執行 stop 。
當要用 recursion 或者任何回圈解決問題,是要想想以下四個條件:

1. 是否必需要 recursion 解決:根據以上 maze 的情況,如不用 recursion ,龜只可以行一步。故此是要用 recursion 解決。
2. base case: 停止執行的情況,如 :n 大於 100 。
3. general case: 通常執行的情況,如 ;n < = 100 。
4. 每次 recursive call 都令問題變細或更接近 base case: 每次 recursive call (maze :n + 5) ,都會令 :n 更接近 base case ,即 :n > 100 。