汉诺塔递归算法

• 算法实现

// 从 a -> b 经过 c 中转
func Hanoi(size int, a, b, c byte) {
	if size == 1 {
		fmt.Printf("%c -> %c\n", a, b)
	} else {
		Hanoi(size-1, a, c, b)
		fmt.Printf("%c -> %c\n", a, b)
		Hanoi(size-1, c, b, a)
	}
}

• 测试代码

func main() {
	function.Hanoi(3, 'A', 'B', 'C')
}

• 结果

A -> B A -> C B -> C A -> B C -> A C -> B A -> B

• 时间复杂度

O(2^n)