0

I understand the concept of recursion and how it stacks up with each call. But I fail to explain how recursive calls are working and gets printed when there are two function call separated by a printf command. Can anyone explain to me how this recursive call is working?

I have found an example regarding a game called "Towers of Hanoi". Ut was used as an example of recursion. The code:

#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);
    }
}

for n=3 it gives output like this

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 //
4

2 回答 2

1

我写这篇文章正是为了回答这样一个问题，我相信很多初学者都会面临这个问题。

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

任务是将 n 个磁盘从 移动L到Rthrough T，可以分解为：

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

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

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

  1. 将顶部磁盘从 移动L到T
  2. 将底部磁盘从 移动L到R
  3. 将顶部磁盘从 移动T到R
于 2014-02-10T15:50:17.087 回答
0

您可能正在考虑一种称为“end-recursive”的特殊变体中的递归！？河内塔算法不是末端递归的。相反，它甚至两次使用递归：

  1. 将磁盘 N 上方的 N-1 个磁盘移动到临时堆栈（第一次 transfer() 函数调用）
  2. 将磁盘 N 移动到目标堆栈 (printf)
  3. 将 N-1 个磁盘从临时堆栈移回目标磁盘 N（第二次 transfer() 函数调用）

transfer() 函数递归背后的想法是：如果使用 n>1 个磁盘调用它以进行操作，它将“工作”委托给自身的递归调用。如果用 n==1 调用它只会移动磁盘。

这是一个修改后的版本，它应该使事情更清楚：

void transfer(int n, char from, char to, char temp)
{
    if (n > 1) {
        // 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);

    if (n > 1) {
        // Move n-1 disks from temporary to destination
        transfer(n - 1, temp, to, from);
    }
}
于 2014-02-10T15:37:21.757 回答