algorithm - 再帰関数で返す

Question

再帰関数を使用するときに return がどのように機能するのか興味があります。たとえば、以下の階乗関数では、実際に計算が行われる前に x が 1 に達します。

int factorial (int x){ 
    if (x==1){
        return 1;     
}else{
    return x * factorial(x - 1);
    }
}

仮定しx = 3ます。ロジックに従うと、3 回ループして 1 を返す必要があるようです。

しかし、もちろん実際には 6 が返されます。

score 1 · Accepted Answer

「その再帰呼び出しからの値は何ですか?」と言うたびにx *、前の反復からを削除しています。それをせずに：

factorial(3)
3 * factorial(2)
3 * (2 * factorial(1))
3 * (2 * 1)
= 6

再帰呼び出しはgoto、新しい引数を使用して関数の先頭に戻るようなものではありません。¹新しい引数を使用して関数を再度呼び出しますが、その呼び出しだけが新しい引数値を持ちます。呼び出し元は、その引数と変数の古い値をまだ持っています。

¹末尾再帰について話している場合を除きますが、これはそうではありません。とにかく、それは単なる最適化です。

score 1 · Accepted Answer

トップに戻るのではなく、factorial関数内で関数を呼び出していfactorialます。

確かに最後は1を返しますが、結果として返すのは行

return x * factorial(x - 1);

への前回の呼び出しのfactorial, wherexは 2 でした.これは 2 * 1 を前回のfactorialwhereへの呼び出し 3 に返しますx.したがって、これは 3 * 2 を与え、関数の最初の呼び出しに結果 - 6 - を返します.

score 0 · Accepted Answer

再帰関数呼び出しは、通常の関数呼び出しと変わりません。したがって、returnある呼び出しのとreturn別の呼び出しのの間に接続はありません。

この例では、最初のreturnステートメントは

return 3 * factorial(2)

factorialこれは、引数 2での呼び出しの戻り値で 3 を乗算します。

しかし factorial(2) の戻り値は

return 2 * factorial(1)

factorialこれは、引数 1での呼び出しの戻り値で 2 を乗算します。

しかし factorial(1) の戻り値は 1 です。

Soreturn 2 * factorial(1)はと同じでreturn 2 * 1、これは 2 です。

Soreturn 3 * factorial(2)はと同じでreturn 3 * 2、これは 6 です。

score 0 · Accepted Answer

最初のステップでは、x = 3. 次に、関数はを返し3 * factorial(2)、それ自体が2 * factorial(1)(xまだ 1 に等しくないため) を返し、最後にfactorial(1)1 を返します。

したがって、最終的には3 * 2 * 1 = 6.

5 に答える 5