递归算法

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

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])

求幂集

LinkList vec

powerset(n):
	if n == S.len:
		output(vec[1..k])
	else:
		k = vec.len
		vec.insert(k+1, S[n])
		powerset(n+1)
		vec.remove(k+1)
		powerset(n+1)

n 皇后问题

走迷宫