3

これは、数値の桁の合計を取得する関数です。

int sumOfDigits(int n)
{
    int sum=0; //line 1
    if(n==0)
        return sum;
    else
    {
        sum=(n%10)+sumOfDigits(n/10); //line 2
        // return sum;  //line 3
    }
}

このコードを書いているときに、ローカル変数のスコープが関数の個々の再帰に対してローカルであることに気付きました。n=11111では、再帰ごとに 5 つsumの変数が作成され、スタックにプッシュされると言うのは正しいでしょうか? これが正しい場合、ループを使用して通常の関数で再帰を使用できる場合、再帰を使用する利点は何ですか?したがって、1つのメモリ位置のみを上書きしますか? ポインターを使用すると、再帰はおそらく通常の関数と同様のメモリを使用します。

2 番目の質問です。この関数は毎回正しい結果を返しますが、再帰 (0 を返す最後のものを除く) が 3 行目のコメントを外さないとどのように値を返すかわかりません (gcc で geany を使用)。

プログラミング初心者ですので、間違っていたらご容赦ください。

4

3 に答える 3

4

では、n=11111 の場合、5 つの合計変数が作成され、再帰ごとにスタックにプッシュされると言うのは正しいでしょうか?

概念的には、コンパイラは再帰のいくつかの形式をジャンプ/ループに変えることがあります。たとえば、末尾呼び出しの最適化を行うコンパイラは、

void rec(int i)
{
    if (i > 0) {
        printf("Hello, level %d!\n", i);
        rec(i - 1);
    }
}

に相当する

void loop(int i)
{
    for (; i > 0; i--)
        printf("Hello, level %d!\n", i);
}

再帰呼び出しが末尾位置にあるため: 呼び出しが行われると、現在の の呼び出しは、呼び出し元recに対する a 以外に行う作業がないreturnため、次の再帰呼び出しのためにスタック フレームを再利用することもできます。

これが正しい場合、ループを使用して通常の関数で再帰を使用できる場合、再帰を使用する利点は何ですか?したがって、1つのメモリ位置のみを上書きしますか? ポインターを使用すると、再帰はおそらく通常の関数と同様のメモリを使用します。

この問題に対して、再帰は、少なくとも C ではかなり不適切です。ループの方がずっと読みやすいからです。ただし、再帰の方が理解しやすいという問題があります。ツリー構造のアルゴリズムがその代表的な例です。

(ただし、すべての再帰は、明示的なスタックを使用したループによってエミュレートできますが、スタック オーバーフローはより簡単にキャッチして処理できます。)

ポインタに関する発言がわかりません。

3行目のコメントを外さない限り、再帰(0を返す最後のものを除く)がどのように値を返すかわかりません。

偶然に。プログラムは未定義の動作を示すため、何でも実行でき、正しい答えを返すことさえあります。

于 2013-06-04T10:20:46.917 に答える
2

では、n=11111 の場合、5 つの合計変数が作成され、再帰ごとにスタックにプッシュされると言うのは正しいでしょうか?

再帰は 5 レベルの深さなので、伝統的に 5 つのスタック フレームが最終的に作成され (ただし、以下を参照してください!)、それぞれにsum変数を保持するためのスペースがあります。したがって、これは精神的にはほとんど正しいです。

これが正しい場合、ループを使用して通常の関数で再帰を使用できる場合、再帰を使用する利点は何ですか?したがって、1つのメモリ位置のみを上書きしますか?

次のようないくつかの理由があります。

  • アルゴリズムを再帰的に表現する方が自然かもしれません。パフォーマンスが許容できる場合は、保守性が非常に重要です
  • 単純な再帰ソリューションは通常、状態を保持しません。つまり、簡単に並列化できることを意味します。これは、マルチコア時代の大きな利点です。
  • コンパイラの最適化は、再帰の欠点をしばしば無効にします

3行目のコメントを外さない限り、再帰(0を返す最後のものを除く)がどのように値を返すかわかりません。

行 3 をコメント アウトするのは未定義の動作です。なぜそうするのですか?

于 2013-06-04T10:18:29.517 に答える
1

はい、パラメーターとローカル変数は各呼び出しに対してローカルであり、これは通常、プログラムスタックに設定された各呼び出し変数のコピーを作成することによって実現されます。はい、ループを使用した実装と比較してより多くのメモリを消費しますが、ループと一定のメモリ使用量で問題を解決できる場合に限ります。ツリーをトラバースすることを検討してください - ツリー要素をどこかに保存する必要があります - スタック上か他の構造か。再帰の利点は、実装が容易であることです (ただし、デバッグが常に容易であるとは限りません)。

2 番目のブランチでコメントreturn sum;すると、動作は未定義です。予期される動作が含まれていれば、何でも起こり得ます。それはあなたがすべきことではありません。

于 2013-06-04T10:20:55.493 に答える