尽管我对递归的理解没有任何问题，但我似乎无法理解河内塔问题的递归解决方案。这是来自维基百科的代码：
procedure Hanoi(n: integer; source, dest, by: char);
Begin
if (n=1) then
writeln('Move the plate from ', source, ' to ', dest)
else begin
Hanoi(n-1, source, by, dest);
writeln('Move the plate from ', source, ' to ', dest);
Hanoi(n-1, by, dest, source);
end;
End;我了解基本情况以及将问题分解成更小部分的概念，直到您能够移动单个磁盘。但是，我无法弄清楚非基本案例中的两个递归调用如何协同工作。也许有人可以帮助我？谢谢。
实际上，您获取该代码的部分也提供了解释：
要将 n 个圆盘从桩 A 移动到桩 C：
- 将 n-1 个圆盘从 A 移动到 B。这将圆盘 #n 单独留在钉子 A 上
- 将圆盘 #n 从 A 移动到 C
- 将 n-1 个圆盘从 B 移到 C 上，使它们位于圆盘 #n 上
很明显，您首先必须移除n - 1 张光盘才能访问第n张光盘。并且您必须首先将它们移动到另一个钉子上，而不是您希望整个塔出现的位置。
除了磁盘的数量之外，您帖子中的代码还有三个参数：一个源peg、一个目标peg 和一个临时peg，可以在其中存储磁盘（每个大小为 n - 1 的磁盘都适合）。
递归实际上发生了两次，一次在 之前writeln，一次在之后。之前的那个writeln会将n - 1 个光盘移动到临时 peg 上，使用目标 peg 作为临时存储（递归调用中的参数顺序不同）。之后，剩余的圆盘将被移动到目标桩，然后第二次递归通过将n - 1 个塔从临时桩移动到目标桩，在盘n 上方，强制移动整个塔。
一年前，我参加了函数式编程课程，并为算法画了这个插图。希望能帮助到你！
(0) _|_ | |
__|__ | |
___|___ | |
____|____ ____|____ ____|____
(1.1) | | |
__|__ | |
___|___ _|_ |
____|____ ____|____ ____|____ (A -> B)
(1.2) | | |
| | |
___|___ _|_ __|__
____|____ ____|____ ____|____ (A -> C)
(1.3) | | |
| | _|_
___|___ | __|__
____|____ ____|____ ____|____ (B -> C)
(2.1) | | |
| | _|_
| ___|___ __|__
____|____ ____|____ ____|____ (A -> B)
(3.1) | | |
| | |
_|_ ___|___ __|__
____|____ ____|____ ____|____ (C -> A)
(3.2) | | |
| __|__ |
_|_ ___|___ |
____|____ ____|____ ____|____ (C -> B)
(3.3) | _|_ |
| __|__ |
| ___|___ |
____|____ ____|____ ____|____ (A -> B)
3 环问题已拆分为 2 个 2 环问题（1.x 和 3.x）
http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html对递归 Hanoi 实现有很好的解释。
总结是，如果你想将底板从棒 A 移动到棒 B，你首先必须将它上面的所有较小的盘子从 A 移动到 C。然后第二个递归调用是移动你移动到 C 的盘子在您的基本案例将单个大盘子从 A 移到 B 之后，回到 B。
我同意，当您第一次看到它时，它并不是立竿见影的，但是当您开始使用它时，它相当简单。
基本情况：您的塔的大小为 1。因此您可以一步完成，从源直接到目标。
递归案例：您的塔的大小为 n > 1。因此，您将大小为 n-1 的顶部塔移动到额外的钉子（by），将大小为 1 的底部“塔”移动到目标钉子，然后移动顶部的塔从 by 到 dest。
所以用一个简单的例子，你有一个高度为 2 的塔：
_|_ | |
__|__ | |
===== ===== =====
第一步：将 2-1 (=1) 的顶部塔移动到额外的钉子（比方说中间的钉子）。
| | |
__|__ _|_ |
===== ===== =====
下一步：将底部圆盘移动到目的地：
| | |
| _|_ __|__
===== ===== =====
最后，将(2-1)=1的顶塔移动到目的地。
| | _|_
| | __|__
===== ===== =====
如果您考虑一下，即使塔有 3 个或更多，也总会有一个空的额外钉子，或者一个带有所有较大圆盘的钉子，供在交换塔时使用的递归。
假设我们想通过 B 将圆盘从 A 移动到 C，那么：
如果您重复上述所有步骤，光盘将传输。
我感到疼痛！
虽然这是一篇旧文章，但我认为人们真正需要理解的不是“将这个移到那个”的方法，而是答案涉及使用递归的副作用。
对我来说非常宝贵的帮助是“The Little Schemer”，它教人们思考和编写递归函数。
然而，这教会了读者在下一次递归调用中使用返回结果的结果。
在河内塔，答案不在于返回结果本身，而在于对返回结果的观察。
魔法发生在函数参数的连续重新排列中。
是的，问题实际上分为三个部分：
在方案中：
(define (th n a b c)
(if (zero? n) 'done
(begin
(th (- n 1) a c b)
(display (list a c))
(newline)
(th (- n 1) b a c))))
(th 5 'source 'spare 'destination)
然而，函数参数的显示是问题的解决方案，并且至关重要的是理解调用的双树状结构。
该解决方案还向所有与传统控制结构搏斗的程序员传达了强大的力量proof by induction和温暖的光芒。
顺便说一句，手动解决问题是相当令人满意的。
最好的方法是始终用同一只手握住顶部圆盘并始终朝同一方向移动那只手。
n光盘的最终移动次数是2^n - 1该move n disc to destination过程的一半。
最后，有趣的是如何向同事、你的妻子/丈夫甚至狗（即使他们不听）解释问题可以巩固启蒙。
在阅读了所有这些解释之后，我想我会权衡一下我的教授用来解释河内塔递归解决方案的方法。这里又是一个算法，n代表环的数量，A、B、C 代表钉子。函数的第一个参数是环数，第二个参数代表源桩，第三个是目的桩，第四个是备用桩。
procedure Hanoi(n, A, B, C);
if n == 1
move ring n from peg A to peg B
else
Hanoi(n-1, A, C, B);
move ring n-1 from A to C
Hanoi(n-1, C, B, A);
end;
我在研究生院被教导永远不要羞于思考小事。那么，让我们看看这个算法，n = 5。首先要问自己的问题是，如果我想将第 5 个环从 A 移动到 B，那么其他 4 个环在哪里？如果第 5 个环占据 peg A，我们想将它移动到 peg B，那么其他 4 个环只能在 peg C 上。在函数Hanoi (n-1, A, C, B)上面的算法中正在尝试将所有其他 4 个环移动到挂钩 C，因此环 5 将能够从 A 移动到 B。按照这个算法，我们查看 n = 4。如果环 4 将从 A 移动到 C，则戒指 3 或更小？它们只能在钉 B 上。接下来，对于 n = 3，如果环 3 将从 A 移动到 B，那么环 2 和环 1 在哪里？当然是在挂钩 C 上。如果你继续遵循这个模式，你可以想象递归算法在做什么。这种方法与新手的方法不同，它首先查看最后一个磁盘，最后查看第一个磁盘。
这里是解释。看图->
通过调用Movetower(3,a,b,c)，您打算将所有 3 个圆盘从一个塔A移到另一个塔B。所以顺序调用是 ->
1. Movetower(3,a,b,c) // No Move needed
2. Movetower(2,a,c,b) // No move needed
3. Movetower(1,a,b,c) // Here is the time to move, move disc1 from a to b
4. Movetower(2,a,c,b) // Returning to this call again, this is the time to move disc2 from a to c
5. Movetower(1,b,c,a) // Again the time to move, this time disc1 from b to c
6. Movetower(3,a,b,c) // Returning to this call again, this is the time to move disc3 from a to b
7. Movetower(2,c,b,a) // Not the time to move
8. Movetower(1,c,a,b) // Here is the time to move, move disc1 from c to a
9. Movetower(2,c,b,a) // Returning to this call again, this is the time to move disc2 from c to b
10.Movetower(1,c,a,b) // Here is the time to move, move disc1 from a to b
希望能帮助到你 ：）
对于动画：https ://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html
将其视为一个堆栈，其中磁盘直径由整数 (4,3,2,1) 表示。第一个递归调用将被调用 3 次，从而填充运行时堆栈，如下所示
在第一次递归结束后，运行时堆栈的内容从最大直径到最小（先进后出）弹出到中间极点。接下来，将直径为 4 的圆盘移动到目的地。
第二个递归调用与第一个相同，只是将元素从中间极点移动到目的地。
第一次递归调用将除最大的部分之外的所有部分从源移动到使用 dest 作为辅助堆。完成后，除了最大的所有部分都将放在旁边，最大的部分是免费的。现在您可以将最大的一个移动到 dest，并使用另一个递归调用将所有部分从 by 移动到 dest。
递归调用对最大的部分一无所知（即他们会忽略它），但这没关系，因为递归调用只会处理较小的部分，因此可以自由地移入和移出最大的部分。
这很简单。假设你想从 A 移动到 C
如果只有一个磁盘，只需移动它。
如果有多个磁盘，请执行
请记住，在移动 n-1 个磁盘时，第 n 个根本不会成为问题（一旦它比所有其他磁盘都大）
请注意，移动 n-1 个磁盘会再次出现相同的问题，直到 n-1 = 1，在这种情况下，您将处于第一个 if（您应该移动它的位置）。
这个问题的答案，程序如何知道，即使是“src”到“aux”，奇数是“src”到“dst”的开局动作在于程序。如果您用 4 个圆盘分解拳头动作，则如下所示：
hanoi(4, "src", "aux", "dst");
if (disc > 0) {
hanoi(3, 'src', 'dst', 'aux');
if (disc > 0) {
hanoi(2, 'src', 'aux', 'dst');
if (disc > 0) {
hanoi(1, 'src', 'dst', 'aux');
if (disc > 0) {
hanoi(0, 'src', 'aux', 'dst');
END
document.writeln("Move disc" + 1 + "from" + Src + "to" + Aux);
hanoi(0, 'aux', 'src', 'dst');
END
}
4盘（偶数）的第一步也是从Src到Aux。
正如我们的一些朋友所建议的，我删除了之前的两个答案，并在这里进行了整合。
这让你有一个清晰的认识。
一般算法是什么......
算法：
solve(n,s,i,d) //solve n discs from s to d, s-source i-intermediate d-destination
{
if(n==0)return;
solve(n-1,s,d,i); // solve n-1 discs from s to i Note:recursive call, not just move
move from s to d; // after moving n-1 discs from s to d, a left disc in s is moved to d
solve(n-1,i,s,d); // we have left n-1 disc in 'i', so bringing it to from i to d (recursive call)
}
这是工作示例单击此处
public static void hanoi(int number, String source, String aux, String dest)
{
if (number == 1)
{
System.out.println(source + " - > "+dest);
}
else{
hanoi(number -1, source, dest, aux);
hanoi(1, source, aux, dest);
hanoi(number -1, aux, source, dest);
}
}
void TOH(int n, int a, int b){
/*Assuming a as source stack numbered as 1, b as spare stack numbered as 2 and c as target stack numbered as 3. So once we know values of a and b, we can determine c as there sum is a constant number (3+2+1=)6.
*/
int c = 6-a-b;
if(n==1){
cout<<"Move from "<<a<<" to "<<b<<"\n";
}
else{
// Move n-1 disks from 1st to 2nd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.
TOH(n-1, a, c);
// Move the last alone disk from 1st to 3rd stack.
TOH(1, a, b);
// Put n-1 disks from 2nd to 3rd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.
TOH(n-1, c, b);
}
}
int main() {
TOH(2, 1, 3);
cout<<"FINISHED \n";
TOH(3, 1, 3);
cout<<"FINISHED \n";
TOH(4, 1, 3);
return 0;
}
共有三座塔，即源塔、目的地塔和辅助塔。源塔拥有所有磁盘，您的目标是将所有磁盘移动到目标塔，并确保在此过程中，您永远不会将较大的磁盘放在较小的磁盘之上。我们可以通过以下步骤使用递归来解决这个问题：
我们在源塔上有n个磁盘
基本情况：n=1 如果源塔中只有一个磁盘，则将其移动到目标塔。
递归情况：n >1
Java中的源代码：
private void towersOfHanoi(int n, char source, char destination, char helper) {
//Base case, If there is only one disk move it direct from source to destination
if(n==1){
System.out.println("Move from "+source+" to "+destination);
}
else{
//Step1: Move the top n-1 disks from source to helper
towersOfHanoi(n-1, source, helper, destination);
//Step2: Move the nth disk from source to destination
System.out.println("Move from "+source+" to "+destination);
/*Step3: Move the n-1 disks(those you moved from source to helper in step1)
* from helper to destination, using source(empty after step2) as helper
*/
towersOfHanoi(n-1, helper, destination, source);
}
}
作为一名 CS 学生，您可能听说过数学归纳法。河内塔的递归解决方案类似地工作 - 唯一不同的部分是真正不会丢失 B 和 C，就像整个塔最终结束一样。
简单来说，这个想法是在三个定义的塔中以与当前盘相同的顺序填充另一个塔，在此过程中的任何时候，较大的盘不会与小盘重叠。
让 'A' 、 'B' 和 'C' 是三个塔。“A”将是最初包含“n”个圆盘的塔。“B”可以用作中间塔，“C”是目标塔。
算法如下：
代码在java中如下：
公共类 TowerOfHanoi {
public void TOH(int n, int A , int B , int C){
if (n>0){
TOH(n-1,A,C,B);
System.out.println("Move a disk from tower "+A +" to tower " + C);
TOH(n-1,B,A,C);
}
}
public static void main(String[] args) {
new TowerOfHanoi().TOH(3, 1, 2, 3);
}
}
这是我使用 golang 递归解决河内塔问题的代码。`包主
import "fmt"
func main() {
toi(4, "src", "dest", "swap")
}
func toi(n int, from, to, swap string) {
if n == 0 {
return
}
if n == 1 {
fmt.Printf("mov %v %v -> %v\n", n, from, to)
return
}
toi(n-1, from, swap, to)
fmt.Printf("mov %v %v -> %v\n", n, from, to)
toi(n-1, swap, to, from)
}`
此 python3 示例使用递归解决方案：
# Hanoi towers puzzle
# for each n, you have to move n-1 disks off the n disk onto another peg
# then you move the n disk to a free peg
# then you move the n-1 disks on the other peg back onto the n disk
def hanoi(n):
if n == 1:
return 1
else:
return hanoi(n-1) + 1 + hanoi(n-1)
for i in range(1, 11):
print(f"n={i}, moves={hanoi(i)}")
输出：
n=1, moves=1
n=2, moves=3
n=3, moves=7
n=4, moves=15
n=5, moves=31
n=6, moves=63
n=7, moves=127
n=8, moves=255
n=9, moves=511
n=10, moves=1023
但当然，计算出多少步的最有效方法是认识到答案总是 1 小于 2^n。所以数学解是 2^n - 1
今天刚看到这个视频：递归“超级力量”（Python）-Computerphile，我认为我们绝对应该在这里拥有Thorsten Altenkirch 教授的代码，因为它是一段非常漂亮和优雅的递归代码，而且我们并不总是有质量要在答案中显示的视频。
def move(f,t) :
print("move disc from {} to {}!".format(f,t))
def hanoi(n,f,h,t) :
if n==0 :
pass
else :
hanoi(n-1,f,t,h)
move(f,t)
hanoi(n-1,h,f,t)
我们的hanoi函数有 4 个参数：
n: 盘数f: 光盘所在的原点(from)h：中间步骤“通过” （助手）t：我们希望光盘最后的最终位置（目标）>>> hanoi(4,"A","B","C")
move disc from A to B!
move disc from A to C!
move disc from B to C!
move disc from A to B!
move disc from C to A!
move disc from C to B!
move disc from A to B!
move disc from A to C!
move disc from B to C!
move disc from B to A!
move disc from C to A!
move disc from B to C!
move disc from A to B!
move disc from A to C!
move disc from B to C!
我在这里对代码做了一个小改动，如果你查看输出，你可以看到小部分模式在父节点中重复（把它想象成分形图像）
def moveTower(height,fromPole, toPole, withPole, ar = ''):
if height >= 1:
print( " "*(3-height), "moveTower:", height, fromPole, toPole, ar )
moveTower(height-1,fromPole,withPole,toPole)
moveDisk(fromPole,toPole,height)
moveTower(height-1,withPole,toPole,fromPole, '*')
#print(withPole)
def moveDisk(fp,tp,height):
print(" "*(4-height), "moving disk", "~"*(height), "from",fp,"to",tp)
moveTower(3,"A","B","C")
输出是：
moveTower: 3 A B
moveTower: 2 A C
moveTower: 1 A B
moving disk ~ from A to B
moving disk ~~ from A to C
moveTower: 1 B C *
moving disk ~ from B to C
moving disk ~~~ from A to B
moveTower: 2 C B *
moveTower: 1 C A
moving disk ~ from C to A
moving disk ~~ from C to B
moveTower: 1 A B *
moving disk ~ from A to B
这是用于递归调用的河内塔的 C++ 代码。
#include <iostream>
void toh(int n, char A, char B, char C) {
if(n == 1) {
std::cout << "Move Disc 1 from " << A << " to " << C << std::endl;
return;
}
toh(n-1, A, C, B);
std::cout << "Move Disc " << n << " from " << A << " to " << C <<std::endl;
toh(n-1, B, A, C);
}
int main() {
int numberOfDisc;
char A = 'A', B = 'B', C = 'C';
std::cout << "Enter the number of disc: ";
std::cin >> numberOfDisc;
toh(numberOfDisc, A, B, C);
return 0;
}
我强烈推荐这个视频，它以一种非常容易理解的方式说明了这个问题的递归。
关键是要了解解决方案中的重复模式。该问题可以分为三个主要的子问题。假设你有 n 个磁盘，它们被放置在杆 A。目标杆是 C，你有 B 作为中间。
主要问题; 使用杆 B 将 n 个圆盘从杆 A 移动到杆 C。
子问题 1 和 3 实际上是在您在上面看到的同一问题划分中解决的。让我们来解决子问题 1。
子问题1；使用棒 C 将 n-1 个圆盘从棒 A 移动到棒 B。
我们解决子问题的方式与解决主要问题的方式相同。我们的基本情况是当磁盘的数量等于 1 时，我们将它从一根杆移动到目标一根，就是这样。
写下这些步骤将大有帮助。
实际上，我在https://helloml.org/tower-of-hanoi-recursion/找到了一个很好的解释。我建议你检查一下。
在本文中，他们提到了解决此问题的步骤。
解决河内塔问题的步骤：
- 将“n-1”盘递归地从源棒移动到辅助棒。
- 将第 n 个圆盘从源棒移动到目标棒。
- 将“n-1”个磁盘递归地从辅助杆移动到目标杆。
它考虑了三个磁盘的情况，并用一组图像解释了算法。
Tower (N,source,aux.dest):
if N =1 Then
Write : Source -> dest
return
end of if
将 N-1 磁盘从 peg 源移动到 peg aux
call Tower (N-1, source, dest, aux)
将 N-1 个磁盘从 peg aux 移动到 peg dest
call Tower (N-1, source, dest, aux)
/** * */ package com.test.recursion;
/** * @author kamals1986 河内塔问题的递归算法 * 算法以幂（2，n）增长。*/ 公共类 TowerOfHanoi {
private static String SOURCE_PEG = "B";
private static String SPARE_PEG = "C";
private static String TARGET_PEG = "A";
public void listSteps(int n, String source, String target, String spare) {
if (n == 1) {
System.out.println("Please move from Peg " + source + "\tTo Peg\t"
+ target);
} else {
listSteps(n - 1, source, spare, target);
listSteps(1, source, target, spare);
listSteps(n - 1, spare, target, source);
}
}
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
new TowerOfHanoi().listSteps(18, SOURCE_PEG, TARGET_PEG, SPARE_PEG);
long endTime = System.currentTimeMillis();
System.out.println("Done in " + (endTime - startTime) / 1000
+ "\t seconds");
}
}
def Hanoi(n, A, B, C):
if(n==1): print "move plates to empty peg"
else:
Hanoi(n-1, A, B, C)
print "move"+str(n)+" to peg "+C
Hanoi(n-1, B, C, A)
我也在尝试递归。
我找到了一种我认为的方式，
我认为它就像一个步骤链（步骤不是恒定的，它可能会根据前一个节点而改变）
我必须弄清楚两件事：
例子
阶乘
1,2,6,24,120 .... 或
1,2*(1),3*(2*1),4*(3*2*1,5*(4*3*2*1)
step=乘以最后一个节点
在这一步之后我需要到达下一个节点，摘要 1
行
function =
n*f(n-1)
its 2 steps process
from a-->to step--->b
我希望这能有所帮助，只考虑 2 thniks，而不是如何从节点到节点，而是节点--> 步骤--> 节点
node-->step 是函数体 step-->node 是另一个函数的参数
再见:) 希望我能帮上忙