The Nature of Code閱讀心得與Python實作：8.2 Recursion

除了自我相似性之外，碎形的另一個基本組成部分是遞迴(recursion)。遞迴指的是，利用稱為製作規則(production rule)的同一套規則，不斷地進行迭代，而且每次迭代時，都會把上一次迭代的結果，作為這次迭代的起點。

自從德國數學家Georg Cantor在1883年介紹了後來被稱為Cantor集(Cantor set)的無限集合(infinite set)後，儘管那時fractal這個字還沒被造出來，但碎形的種子就此在現代數學中生根、發芽。Cantor用來製作Cantor集的方法非常簡單，就只是運用遞迴的方式，不斷地把線段三等分並挖掉中間那部分而已；如下圖所示：

Cantor在製造Cantor集時，是假設遞迴過程不斷地進行下去永不止歇，這樣才能得到無限集合。當然啦，這種無限的過程，就只存在數學家的抽象思維中，在真實世界是不存在的。所以，在寫程式以遞迴來處理問題時，必須設定好，在特定的條件下，遞迴必須終止，不再繼續下去；這個特定的條件就叫做基底情況(base case)，因為已經做到底了，夠了！不能再繼續下去了，該停了！那如果不設定基底情況會怎樣？程式會像無窮迴圈一樣，一直一直的跑下去嗎？當然不會！遞迴程式最後不是把系統的資源給吃光，就是會因為超過能夠允許的遞迴深度上限值而出現錯誤。

Implementing Recursive Functions

遞迴函數指的是會呼叫自己的函數；通常長這樣：

def some_function():
    :
    some_function()

最常被用來說明遞迴函數運算方式的，應該就是數學上的階乘(factorial)了。對於正整數n而言，其階乘記為n!，並定義為：

n! = n × (n−1) × (n−2) × ⋯ × 3 × 2 × 1

另外，0的階乘定義為

0! = 1

從定義就可以推導出，對於正整數n而言

n! = n × (n−1)!

這條式子挺簡單的，不過也就是這條式子，讓階乘成為解釋遞迴函數時的最佳代言人。怎麼說呢？把式子再詳細拆解下去就知道了：

    n! = n × (n−1)! 
(n−1)! = (n−1) × (n−2)! 
(n−2)! = (n−2) × (n−3)!
       :
       :
    3! = 3 × 2! 
    2! = 2 × 1!
    1! = 1

上面這一大串式子，不就是遞迴的過程嗎？寫成程式，可以這樣寫：

def factorial(n):
    # 基底情況
    if n in (0, 1):
        return 1
    
    return n*factorial(n-1)

從實際的例子來看，會更容易了解這個遞迴函數的運作方式。假設我們要計算$3!$，呼叫factorial(3)之後，整個運作過程是這樣的：

factorial(3)                      6
    ↓                             ↑
return 3*factorial(2)            3*2 
             ↓                    ↑
         return 2*factorial(1)   2*1
                      ↓           ↑
                  return 1 -----> 1

從這裡也可以看出來，遞迴就是一層一層的呼叫下去；越來越深、越來越深，深到抵達基底情況才停止。所以說，基底情況就是整個遞迴大廈的地基，是最底部的結構，再下去就沒東西了。沒有基底情況這個地基，遞迴大廈是蓋不起來的；這或許就是為什麼要用「base」這個字來描述這個地基的原因吧。

計算階乘除了用遞迴來寫之外，當然也可以用迴圈來寫：

def factorial(n):
    if n in (0, 1):
        return 1
    
    f = n
    for i in range(n-1, 1, -1):
        f *= i
        
    return f    

事實上，用遞迴寫的東西，改用迴圈寫也可以，只不過用遞迴來寫會比較直覺，程式的可讀性也比較好；但是，有一好沒兩好，遞迴的效率通常會比迴圈差，也會佔用比較多的記憶體。

在結束階乘這個話題前必須提醒一下，上面計算階乘的函數factorial()，不管是遞迴版或迴圈版，因為主要是要說明遞迴是什麼，所以就都沒有去判斷使用者給的n是不是0或正整數，以免不相干的程式碼影響說明及閱讀。比較完整的寫法，這部分還是應該要加上去。

接下來，就用遞迴的方式來畫些漂亮的圖案。

Example 8.1: Recursive Circles Once

def draw_circles(surface, x, y, radius):
    # 基底情況
    if radius < 4:
        return
        
    pygame.draw.circle(surface, (0, 0, 0), (x, y), radius, 1)
    
    radius *= 0.75
    # 呼叫自己來畫圓心位置相同，但半徑比較小的圓
    draw_circles(surface, x, y, radius)


# python version 3.10.9
import sys

import pygame  # version 2.3.0

    
pygame.init()

pygame.display.set_caption("Example 8.1: Recursive Circles Once")

WHITE = (255, 255, 255)

screen_size = WIDTH, HEIGHT = 640, 240
screen = pygame.display.set_mode(screen_size)

FPS = 30
frame_rate = pygame.time.Clock()

screen.fill(WHITE)

draw_circles(screen, WIDTH//2, HEIGHT//2, WIDTH//2)

while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()  
    
    pygame.display.update()
    frame_rate.tick(FPS)

Example 8.2: Recursive Circles Twice

遞迴時，可以呼叫自己不止一次。在這個例子中是呼叫自己兩次，在左、右畫出比較小的圓。

def draw_circles(surface, x, y, radius):
    # 基底情況
    if radius < 4:
        return
        
    pygame.draw.circle(surface, (0, 0, 0), (x, y), radius, 1)
    
    # 呼叫自己，在左、右畫半徑比較小的圓
    draw_circles(surface, x-radius/2, y, radius/2)
    draw_circles(surface, x+radius/2, y, radius/2)


# python version 3.10.9
import sys

import pygame  # version 2.3.0

    
pygame.init()

pygame.display.set_caption("Example 8.2: Recursive Circles Twice")

WHITE = (255, 255, 255)

screen_size = WIDTH, HEIGHT = 640, 240
screen = pygame.display.set_mode(screen_size)

FPS = 30
frame_rate = pygame.time.Clock()

screen.fill(WHITE)

draw_circles(screen, WIDTH//2, HEIGHT//2, WIDTH//2)

while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()  

    pygame.display.update()
    frame_rate.tick(FPS)

Example 8.3: Recursive Circles Four Times

呼叫自己四次，在左、右、上、下畫出比較小的圓。

def draw_circles(surface, x, y, radius):
    # 基底情況
    if radius < 16:
        return
        
    pygame.draw.circle(surface, (0, 0, 0), (x, y), radius, 1)
    
    # 呼叫自己，在左、右、上、下畫半徑比較小的圓
    draw_circles(surface, x-radius/2, y, radius/2)
    draw_circles(surface, x+radius/2, y, radius/2)
    draw_circles(surface, x, y-radius/2, radius/2)
    draw_circles(surface, x, y+radius/2, radius/2)


# python version 3.10.9
import sys

import pygame  # version 2.3.0
 
  
pygame.init()

pygame.display.set_caption("Example 8.3: Recursive Circles Four Times")

WHITE = (255, 255, 255)

screen_size = WIDTH, HEIGHT = 640, 240
screen = pygame.display.set_mode(screen_size)

FPS = 30
frame_rate = pygame.time.Clock()

screen.fill(WHITE)

draw_circles(screen, WIDTH//2, HEIGHT//2, WIDTH//2)

while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()  

    pygame.display.update()
    frame_rate.tick(FPS)

Drawing the Cantor Set with Recursion

先前提到過Cantor集，現在就來寫個畫Cantor集的遞迴函數。

製作Cantor集的基本動作，也就是製作規則，是把一條線段三等分，然後挖掉中間那部分；不斷地針對剩下的線段重複這個基本動作，就可以得到Cantor集了。不過，在寫程式畫Cantor集時，因為我們是要把每一次做完基本動作之後的結果都畫出來，所以並不需要那麼麻煩，先把線段畫出來，然後再塗掉中間那部分；我們可以就只畫出左、右兩條線段就可以了，反正結果都一樣。

原理很簡單，那程式要怎麼寫呢？第一步，當然是要畫出一條線段囉。程式可以這樣寫：

def cantor(surface, x, y, length):
    pygame.draw.line(surface, (0, 0, 0), (x, y), (x+length, y))

這樣就可以呼叫cantor()來畫出一條起點為(x, y)，長度為length的水平線段了。

畫好一條線段之後，再來就是要畫左、右兩條長度為length/3的線段。在這裡要注意一下，這兩條線段要畫在原來那條線段下面一點的地方，要不然所有的線都疊在一起，看起來就跟原來那條線段沒兩樣；有畫等於沒畫。假設我們要把這兩條線段畫在原來那條線段下面20個像素的位置，那這兩條線段的起點位置會在(x, y+20)及(x+2*length/3, y+20)。加入這部分程式的cantor()，會變成

def cantor(surface, x, y, length):
    pygame.draw.line(surface, (0, 0, 0), (x, y), (x+length, y))
    
    cantor(surface, x, y+20, length/3)
    cantor(surface, x+2*length/3, y+20, length/3)

當呼叫cantor()之後，會用pygame.draw.line()畫出一條線段，接著又呼叫cantor()，除了在下方畫出較短的線段之外，還會再呼叫cantor()。這時候，除了在更下方畫出更短的線段外，還會再呼叫cantor()。如此這般，就這樣不斷地輪迴下去，展現出遞迴的本色。

處理完畫線的部分後，最後在cantor()中，還得加上基底情況，以免無窮地遞迴下去。假設我們希望線段的長度小於2個像素時就停止遞迴，不再繼續畫出任何線段；加上這個基底情況後，完整的cantor()長這樣：

def cantor(surface, x, y, length):
    # 基底情況
    if length < 2:
        return
        
    pygame.draw.line(surface, (0, 0, 0), (x, y), (x+length, y))
    
    cantor(surface, x, y+20, length/3)
    cantor(surface, x+2*length/3, y+20, length/3)

下面這個例子，就是利用cantor()來畫出Cantor集。

Example 8.4: The Cantor Set

主程式如下：

# python version 3.10.9
import sys

import pygame  # version 2.3.0
  
  
pygame.init()

pygame.display.set_caption("Example 8.4: The Cantor Set")

WHITE = (255, 255, 255)

screen_size = WIDTH, HEIGHT = 640, 120
screen = pygame.display.set_mode(screen_size)

FPS = 30
frame_rate = pygame.time.Clock()

screen.fill(WHITE)

cantor(screen, 10, 10, 620)

while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()  

    pygame.display.update()
    frame_rate.tick(FPS)

Exercise 8.1

在H字形圖案兩條垂直線的4個端點，畫上比較小的H字形圖案；不斷地重複這個步驟就可以了。

def draw_Hs(surface, x, y, width, height):
    # 基底情況
    if width < 4:
        return
    
    # 畫H字形圖案
    hx, hy = width/2, height/2
    pygame.draw.line(surface, (0, 0, 0), (x-hx, y), (x+hx, y))
    pygame.draw.line(surface, (0, 0, 0), (x-hx, y-hy), (x-hx, y+hy))
    pygame.draw.line(surface, (0, 0, 0), (x+hx, y-hy), (x+hx, y+hy))

    # 在H字形圖案的垂直線段端點畫小一點的H字形圖案    
    width *= 0.45
    height *= 0.45
    draw_Hs(surface, x-hx, y-hy, width, height)
    draw_Hs(surface, x-hx, y+hy, width, height)
    draw_Hs(surface, x+hx, y-hy, width, height)
    draw_Hs(surface, x+hx, y+hy, width, height)

        
# python version 3.10.9
import sys

import pygame  # version 2.3.0
  
  
pygame.init()

pygame.display.set_caption("Exercise 8.1")

WHITE = (255, 255, 255)

screen_size = WIDTH, HEIGHT = 640, 320
screen = pygame.display.set_mode(screen_size)

FPS = 30
frame_rate = pygame.time.Clock()

screen.fill(WHITE)

draw_Hs(screen, WIDTH/2, HEIGHT/2, WIDTH/2, HEIGHT/2)

while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()  

    pygame.display.update()
    frame_rate.tick(FPS)