递归【汉塔罗问题】

汉诺塔（Hanoi Tower）问题是一个著名的递归问题，最初由法国数学家Édouard Lucas在1883年发明。这个问题描述如下：
有三根柱子A、B、C，以及n个不同大小的圆盘，初始时所有的圆盘都按照从大到小的顺序放在柱子A上。目标是将所有圆盘移到柱子C上，同时遵循以下规则：
- 每次只能移动一个圆盘。
- 在任何时候，都不能将一个较大的圆盘放在一个较小的圆盘上面。

递归算法是解决汉诺塔问题的自然方式。

代码

def hanoi(n,A,B,C):#定义汉诺塔函数,参数n是圆盘数，A、B、C是3根柱
	if n==1:#判断圆盘数，如果等于1
		print(A,'-->',C,' ',n) # 直接将A柱上的圆盘移动到C柱上
	else:#否则，进行递归移动
		hanoi(n-1,A,C,B) #递归将A柱最上方的n-1个盘子落在B柱
		print(A,'-->',C,' ',n) # 输出将A柱上的圆盘移动到C柱上,也就是将A柱的最小面盘子落在C柱
		hanoi(n-1,B,A,C) #递归将B柱上的n-1个盘子，落在C柱

hanoi(3,'A','B','C')#调用函数

代码解释

函数hanoi(n, A, B, C)接受四个参数：

• n：圆盘的数量。
• A：起始柱子，初始时所有圆盘位于此柱子上。
• B：辅助柱子，用于临时存放圆盘。
• C：目标柱子，最终所有圆盘应位于此柱子上。

递归步骤：

• 基本情况：如果只有一个圆盘（n == 1），则直接从柱子A移动到柱子C。
• 递归情况：
  • 首先，递归地将n-1个圆盘从柱子A移动到柱子B，使用柱子C作为辅助柱子。这一步骤将除了底部最大的圆盘以外的所有圆盘移动到柱子B。
  • 接着，将底部最大的圆盘从柱子A直接移动到柱子C。
  • 最后，再递归地将n-1个圆盘从柱子B移动到柱子C，这次使用柱子A作为辅助柱子，完成整个过程。

调用函数：

hanoi(3, 'A', 'B', 'C')

这行代码调用了hanoi函数，尝试解决3个圆盘的汉诺塔问题，从柱子A开始，通过柱子B，目标是柱子C。

递归算法的优点是代码简洁且逻辑清晰，但缺点是在n较大时，计算量会呈指数级增长，可能会导致大量的函数调用，影响程序的执行效率和内存使用。