線上教材：Python 程式設計

如果一個函式，會呼叫到自己本身，那麼這個函式就是遞迴函式。關於遞迴，在生活中就有一些常見的例子，比如說：
從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？「從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？「從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？「從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？「 ......」」」」

或者是：

當然，對自己呼叫不會是無窮盡的，到某個條件成立時，就必須停下來，例如遞迴披薩（以披薩為配料的披薩）：

數學上也有非常多關於遞迴的式子，例如階乘的「f(1) = 1，f(n) = n * f(n-1)」，以及費氏數列的「f(1) = f(2) = 1，f(n) = f(n - 1) + f(n - 2)」等等。而遞迴在計算機科學上的定義，是將一個問題，分解成數個較小的問題求解，由小問題的解答，推出大問題的解答。雖然能用遞迴解決的問題，也都可以用迴圈解決；但有些問題，使用遞迴的方式來思考與求解，會比較直覺明瞭。但是，由於重複呼叫函式，所以遞迴容易造成系統多於的負擔，使用上必須注意。以下將用幾個簡單的範例，介紹遞迴的寫法。

雖然 Python 有內建函式可以計算階乘，但作為必須要簡單一點的第一個範例，以下將展示如何撰寫遞迴函式計算階乘：
def factorial(n):
	if n == 1:
		return 1
	return n * factorial(n - 1)


if __name__ == '__main__':
	print(factorial(5))
在上述範例中，第 2 及第 3 行是遞迴的終止條件，遞迴函式一定要有終止條件，否則無窮盡的呼叫，很快就會耗光系統資源。第 4 行則是對自己的呼叫，例如傳入 n = 5 時，在這行會呼叫 factorial(4)。而整個呼叫過程，可以用下圖表達：

以下程式，會用遞迴的方法計算費氏數列：
def fibonacci(n):
	if n == 1 or n == 2:
		return 1
	return fibonacci(n - 1) + fibonacci(n - 2)


if __name__ == '__main__':
	print(fibonacci(5))
上述範例的整個呼叫過程，可以用下圖表達，其中黑色箭頭代表呼叫，紅色箭頭代表回傳，回色箭頭旁邊的數字代表該次回傳的值。順序的規則是，有黑色箭頭可以往下時就要先往下（能先呼叫就要先呼叫），左右同時有黑色箭頭時要先走左邊（加法的左右兩邊是左邊先算），黑色都走完了才能走紅色（呼叫都結束了才能回傳）：

組合個數的遞迴式為 C(m, n) = C(m - 1, n - 1) + C(m - 1, n)，亦即分成「現在這個要選」以及「現在這個不選」的兩種狀況來分別進行遞迴。撰寫成程式則如以下：
def combo(m, n):
	if n == 1:
		return m
	elif m == n or n == 0:
		return 1
	return combo(m - 1, n - 1) + combo(m - 1, n)


if __name__ == '__main__':
	print(combo(5, 3))
上述範例的整個呼叫過程，可以用下圖表達，圖示與上一個範例相同。你可以發現這兩個範例都有非常多部分的計算重複了，若需要使用遞迴，但是又要緩解甚至避免此種情況的話，你可以建立一個全域的串列或字典來儲存算過的內容，如果算過了就直接取用，不進行遞迴；也可以加入更多的終止條件，例如以組合個數來說，你知道當 m == n + 1 的時候有 m 種可能，就可以把這條規則也加入終止條件，則遞迴的進行就會只到下圖的藍線為止：

如果你希望的是在一個有 m 個元素的串列當中，列出所有取 n 個不同元素的狀況的話，則除了利用內建的 itertools.combinations 以外，也可以撰寫如下：
def list_combo(items, n):
	if len(items) < n:
		return []
	if len(items) == n:
		return [items]
	if n == 0:
		return [[]]
	if n <= 1:
		return [[item] for item in items]

	with_first = [[items[0]] + c for c in list_combo(items[1:], n-1)]
	without_first = list_combo(items[1:], n)
	return with_first + without_first


if __name__ == '__main__':
	print(list_combo([1, 2, 3, 4, 5], 3))
上述範例為了遞迴數的方便繪製，所以根據組合的數學特性，多加了一些終止條件，例如 C m 取 1 的時候，是每個元素各別都要選，以及 m 與 n 相等時是全部的元素都要一起選。其整個呼叫過程，可以用下圖表達：

在 Python 當中的最大公因數（greatest common divisor, gcd）也有內建函式可以使用，但你如果會關心怎樣用遞迴自己寫的話，則可以使用 gcd(a, b) = gcd(b, a % b) 這個遞迴式來撰寫，其實就是我們以前都學過的輾轉相除法，如下：
def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)


if __name__ == '__main__':
	print(gcd(100, 60))
河內塔也很容易用遞迴求解。例如在兩個盤子的情況下，你可以這樣做（假設左邊的柱子為起始點）：

把小盤搬到中間（暫存柱）

把大盤搬到右邊（目標柱）

把小盤也搬到右邊，完成

因此，對於遞廻來說，只要把上面範例的小盤子，當成 n-1 個小盤子就好了。這個意思是說，我們可以把問題拆解成 1 個大盤子和 n-1 個比較小的盤子，至於 n-1 個小盤子的搬法，就交給遞迴解決。整體的步驟如下：

把 n-1 個盤子，從「起始柱」移到「暫存柱」

把第 n 個盤子移到「目標柱」

把「暫存柱」的那 n-1 個盤子移到「目標柱」
def hanoi(n, start_rod, temp_rod, target_rod):
	if n > 0:
		hanoi(n-1, start_rod, target_rod, temp_rod)
		print('Move dish {} from rod {} to rod {}'.format(n, start_rod, target_rod))
		hanoi(n-1, temp_rod, start_rod, target_rod)


if __name__ == '__main__':
	hanoi(3, 1, 2, 3)
遞迴除了用於計算和列舉以外，也可以用來做搜尋。例如有個經典的數學遊戲「24 game」，其內容是給你四個數字，問有沒有辦法透過這四個數字之間的運算，來產生 24 這個數字；例如 [8, 9, 6, 4] 這四個數字，可以用 8 * 9 / 4 + 6 的方式得到 24，而 [3, 5, 7, 7] 這四個數字，則無論怎樣組合，都無法得到 24。這個遊戲很適合利用遞迴來做搜尋，範例如下：
def game_24(nums):
	EPS = 1e-5
	if len(nums) == 1:
		return abs(nums[0] - 24.0) < EPS

	for i in range(len(nums)):
		for j in range(len(nums)):
			if i == j:
				continue
			next_nums = [nums[k] for k in range(len(nums)) if k != i and k != j]
			a, b = nums[i], nums[j]
			candidates = [a + b, a - b, b - a, a * b]
			if abs(b) > EPS:
				candidates.append(a / b)
			if abs(a) > EPS:
				candidates.append(b / a)

			for val in candidates:
				if game_24([val] + next_nums):
					return True
	return False

if __name__ == '__main__':
	print(game_24([8, 9, 6, 4]))
上述範例中的遞迴方式，是每次挑選兩個不同位置的數字，並做各種可行的運算來組成新的數字，再一一的問這些新數字，能否跟剩下的數字組合出 24；而遞迴的終止條件，就是當數字個數只剩一個時，如果它是 24 就成功，否則就失敗。至於呼叫的過程，以 game_24([8, 9, 6, 4]) 來說，它會依次呼叫：

i = 0, j = 1 時的 game_24([8+9, 6, 4])

i = 0, j = 1 時的 game_24([8-9, 6, 4])

i = 0, j = 1 時的 game_24([9-8, 6, 4])

...

i = 3, j = 2 時的 game_24([6 * 4, 8, 9])

i = 3, j = 2 時的 game_24([6 / 4, 8, 9])

i = 3, j = 2 時的 game_24([4 / 6, 8, 9])

而該層首個被呼叫的 game_24([8+9, 6, 4])，即 game_24([17, 6, 4])，則會依次呼叫：

i = 0, j = 1 時的 game_24([17+6, 4])

i = 0, j = 1 時的 game_24([17-6, 4])

i = 0, j = 1 時的 game_24([6-17, 4])

...

而如果你希望遞迴函式不只是回答是否有解，而是要找出至少一組解的話，程式架構也非常相似，只需要把算式跟計算結果一起在遞迴中傳遞即可，範例如下：
def game_24(nums, expr=[]):
	EPS = 1e-5
	if len(nums) == 1:
		return abs(nums[0] - 24.0) < EPS, expr

	if not expr:
		expr = list(map(str, nums))

	for i in range(len(nums)):
		for j in range(len(nums)):
			if i == j:
				continue
			next_nums = [nums[k] for k in range(len(nums)) if k != i and k != j]
			next_exprs = [expr[k] for k in range(len(expr)) if k != i and k != j]
			a, b = nums[i], nums[j]
			x, y = expr[i], expr[j]
			candidates_nums = [a + b, a - b, b - a, a * b]
			candidates_exprs = [f'(({x})+({y}))', f'(({x})-({y}))', f'(({y})-({x}))', f'(({x})*({y}))']
			if abs(b) > EPS:
				candidates_nums.append(a / b)
				candidates_exprs.append(f'(({x})/({y}))')
			if abs(a) > EPS:
				candidates_nums.append(b / a)
				candidates_exprs.append(f'(({y})/({x}))')

			for val, exp in zip(candidates_nums, candidates_exprs):
				is_24, the_exp = game_24(
					[val] + next_nums,
					expr=[exp]+next_exprs
				)
				if is_24:
					return True, the_exp
	return False, ''

if __name__ == '__main__':
	print(game_24([8, 9, 6, 4]))
在上述範例中，我們採取的是把括號加好加滿的策略，來避免算式的實際意義，與它希望被代表的意義不同；你如果希望少加一點括號，則需要根據運算優先權等原則，另外撰寫邏輯判斷，或者等到計算完成後，以其他的方法處理。另外，如果你有興趣，也可以再去瞭解看看要怎樣找出所有解。