递归算法

递归算法的正确性容易用数学归纳法得到证明.

Hanoi 塔

# 将 n 个圆盘从 x 搬到 z; y 作为辅助.
hanoi(n, x, y, z):
	if n == 1:
		print(x, " -> ", z)
	else:
		hanoi(n-1, x, z, y)
		print(x, " -> ", z)
		hanoi(n-1, y, x, z)

九连环

# 取下前 n 个环
unload(n):
	if n == 1:
		print("unload #1")
	elif n == 2:
		print("unload #2")
		print("unload #1")
	else:
		unload(n-2)
		print("unload #", n)
		load(n-2)
		unload(n-1)

# 装上前 n 个环
load(n):
	if n == 1:
		print("load #1")
	elif n == 2:
		print("load #1")
		print("load #2")
	else:
		load(n-1)
		unload(n-2)
		print("load #", n)
		load(n-2)

回溯算法

traceback(n):
	if n == MAX_DEPTH:
		output(vec)
	else:
		for move in possible_moves:
			move(vec[n])
			traceback(n+1)
			unmove(vec[n])

全排列 输入一个数组 arr, 输出它的全排列.

遍历子集 输入一个数组 arr, 输出它的全部子集.

`k`-子集 输入一个数组 arr 和一个数字 k, 输出数组的所有大小为 k 的子集.

n 皇后问题

走迷宫