0

再帰の概念と、各呼び出しで再帰がどのように積み重なっていくかを理解しています。しかし、printf コマンドで区切られた 2 つの関数呼び出しがある場合に、再帰呼び出しがどのように機能し、出力されるかを説明できません。この再帰呼び出しがどのように機能するかを誰かに説明してもらえますか?

「タワーズ オブ ハノイ」というゲームに関する例を見つけました。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このような出力が得られるため

ディスク 1 を L から R に移動 //
ディスク 2 を L から C に移動 //
ディスク 1 を R から C に移動 //
ディスク 3 を L から R に移動 //
ディスク 1 を C から L に移動 //
ディスク 2 を C から R に移動 //
ディスク 1 を L から R に移動 //
4

2 に答える 2

0

「end-recursive」と呼ばれる特別なバリアントでの再帰を考えているかもしれません!? ハノイの塔アルゴリズムは終了再帰的ではありません。代わりに、再帰を 2 回も使用します。

  1. ディスク N の上の N-1 個のディスクを一時スタックに移動します (最初の transfer() 関数呼び出し)
  2. ディスク N を目的のスタックに移動する (printf)
  3. N-1 個のディスクを一時スタックから宛先ディスク N に戻します (2 回目の 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 に答える