0

誰か説明してくれませんか？C# で次のような数値の階乗を計算する関数を作成しました。

public int factorial(int input)
{
    if (input == 0 || input == 1)
        return 1;
else
{
    int temp = 1;
    for (int i = 1; i <= input; i++)
        temp = temp * i;
    return temp;
    }
}

しかし、再帰ループを使用して階乗を見つける C++ コードをいくつか見つけました (C++ はまったく知りません)。

int factorial(int number) {
 int temp;
 if(number <= 1) return 1;
 temp = number * factorial(number - 1);
 return temp;
}

誰かが私にそれがどのように機能するか説明できますか? ありがとう。

4

5 に答える 5

6

まあ、それは の基本ケースであるという事実を使用factorial(n)しn * factorial(n - 1)ますn = 1。

たとえば、次のようになります。

factorial(5) = 5 * factorial(4)
             = 5 * 4 * factorial(3)
             = 5 * 4 * 3 * factorial(2)
             = 5 * 4 * 3 * 2 * factorial(1)
             = 5 * 4 * 3 * 2 * 1

実装は、この再帰的な定義を使用するだけです。

于 2011-04-24T13:01:16.467 に答える
2

これを行ごとに分析してみましょう。

if(number <= 1) return 1;
temp = number * factorial(number - 1);
return temp;

行 1: 数値が 0 以下の場合、1 を返します。これは0! = 1、1! = 1

行 2 + 3: そうでない場合は を返しnumber * factorial(number - 1)ます。これを見てみましょう5!（ここでは、簡潔にするためにn!同義語として使用します）factorial(n)

5!
5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 3 * 1 // Here we don't have to expand 1! in the same way because of the condition

それで全体が広がっていきます。そのプロパティを使用するだけです

n! = n * (n - 1) * ... * 2 * 1 = n * (n - 1)!

警告: 再帰コードは、いつものように、反復 (または末尾再帰最適化) バージョンと比較して、スタック オーバーフローとメモリ使用量の増加の影響を受けるため、自己責任で使用してください。

于 2011-04-24T13:02:17.097 に答える
2

構文的には、C++ コードは C# で記述された同じコードと同じです。言語の不一致に不意を突かれないようにしてください。変数が関数の先頭で宣言されていることを考えると、実際には C のように見えます。これは、C++ または C# では厳密には必要ありません。私は、変数を初めて使用するときに変数を宣言し、宣言と初期化を 1 つのステートメントにまとめることを好みますが、それはコードの機能を変更しないスタイル上の好みにすぎません。

コード スニペットの各行にコメントを追加して、これを説明します。

// Declare a function named "Factorial" that accepts a single integer parameter,
// and returns an integer value.
int Factorial(int number)
{
    // Declare a temporary variable of type integer
    int temp;

    // This is a guard clause that returns from the function immediately
    // if the value of the argument is less than or equal to 1.
    // In that case, it simply returns a value of 1.
    // (This is important to prevent the function from recursively calling itself
    // forever, producing an infinite loop!)
    if(number <= 1) return 1;

    // Set the value of the temp variable equal to the value of the argument
    // multiplied by a recursive call to the Factorial function
    temp = number * Factorial(number - 1);

    // Return the value of the temporary variable
   return temp;
}

再帰呼び出しとは、関数が同じ関数内から自分自身を呼び出すことを意味します。これが機能するのは、n の階乗が次のステートメントと同等であるためです。

n! = n * (n-1)!

コードがどのように機能するかを理解するための優れた方法の 1 つは、コードをテスト プロジェクトに追加し、デバッガーを使用してコードを 1 ステップ実行することです。Visual Studio は、C# アプリケーションでこれを非常に豊富にサポートしています。関数がどのように再帰的に自身を呼び出すか、各行が順番に実行されるのを観察し、操作が実行されると変数の値が変化するのを観察することさえできます。

于 2011-04-24T13:03:51.303 に答える
1

再帰関数は、本体で自分自身を呼び出す関数です。制限され、最終的に値を返すには、次の 2 つのことが発生する必要があります。

  1. 自分自身を再度呼び出さず、既知の値を返す基本ケースが必要です。この基本ケースは再帰を停止します。階乗関数の場合、入力が 0 の場合、この値は 1 です。

  2. その再帰的なアプリケーションは、基本ケースに収束する必要があります。階乗の場合、再帰アプリケーションは、入力から 1 を引いた関数を呼び出し、最終的に基本ケースに収束します。

この関数をより簡単に見るには、次のようにします (正の入力に対してのみ有効です)。

int factorial(int input) {
  return input == 0 ? 1 : input * factorial(input - 1);
}
于 2011-04-24T13:10:32.580 に答える
1

再帰関数は同じ関数から呼び出す関数です

例えば：

  Test()
    {
      i++;
      Test();
      cout<<i;
    }

関数を何度も呼び出すコードを見てください

再帰の問題は無限に機能するので、特定の条件で停止したい

上記のコードの一部が変更されました

int i=0; 
Test()
        {
         if(i==10) return;
         i++;
         Test();
         cout<<i;
        }

output は 10 になります 10 回印刷されます。ここでは、この行cout<<i; は return 後に実行されます

于 2011-04-24T13:53:41.060 に答える