c - 需要解释 "Towers of Hanoi"中的递归调用

Question

我理解递归的概念以及它如何与每次调用叠加。但我无法解释当有两个函数调用由 printf 命令分隔时，递归调用如何工作并打印。谁能向我解释一下这个递归调用是如何工作的？

我找到了一个关于名为“Towers of Hanoi”的游戏的示例。 Ut 被用作递归的示例。代码:

#include <stdio.h>

void transfer(int n, char from, char to, char temp);

int main()
{
    int n;

    printf("how many disk");
    scanf("%d", &n);
    printf("\n");
    transfer(n, 'L', 'R', 'C');
    return 0;
}

/*
 * n = number of disk,
 * from = origin,
 * to = destination,
 * temp = temporary storage
 */
void transfer(int n, char from, char to, char temp)
{
    if (n > 0) {
        // Move n-1 disks from origin to temporary
        transfer(n - 1, from, temp, to);

        // Move n th disk from origin to destination
        printf("move disk %d from %c to %c\n", n, from, to);

        // Move n-1 disks from temporary to destination
        transfer(n - 1, temp, to, from);
    }
}

对于n=3它给出这样的输出

move disk 1 from L to R //move disk 2 from L to C // move disk 1 from R to C // move disk 3 from L to R // move disk 1 form C to L // move disk 2 from C to R //move disk 1 from L to R //

Answer 1

我写了this post准确回答这样一个问题，我相信很多初学者都会面临这个问题。

当您有 n 个磁盘时会发生什么。

任务是通过 T 将 n 个磁盘从 L 移动到 R ，可以分解为:

1. 将顶部的 n-1 个磁盘从 L 移动到 T
2. 将底部圆盘从L移动到R
3. 将 n-1 个磁盘从 T 移动到 R

现在请注意，步骤 1 和 3 本身就是一个汉诺塔问题，具有 n-1 个圆盘以及不同的源极和目标极。第 1 步是通过 R 将 n-1 个磁盘从 L 移动到 T 的问题，第 2 步是移动 的问题n-1 个磁盘，从 T 到 R 到 L。

这样问题就被分解为可以一步解决的子问题，这是一个 2 磁盘问题实例。

1. 将顶部磁盘从L移动到T
2. 将底部圆盘从L移动到R
3. 将顶部磁盘从 T 移动到 R