递归算法的正确性容易用数学归纳法得到证明.
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 皇后问题
走迷宫