この関数はなぜ私に無限ループを与えていますか？

Question

int bar(int val) { 
    int x = 0; 
    while(val > 0) { 
     x= x + bar(val-1); 
    } 
    return val; 
} 

私はこの関数をbar(3)と呼びます。それは無限ループに入っています。どうして？

Answer 1

は、ここで（表現valとval - 1は、各反復のための彼らの実際の値に置き換えられている）それはそれを説明するのに役立つことが起こっているの可視化です：

bar(3): while (3 > 0) { x = x + bar(2); } 
    bar(2): while (2 > 0) { x = x + bar(1); } 
    bar(1): while (1 > 0) { x = x + bar(0); } 
     bar(0): return 0; 
    bar(1); while (1 > 0) { x = x + bar(0); } 
     bar(0): return 0; 
    bar(1): while (1 > 0) { x = x + bar(0); } 
     bar(0); return 0; 

うまくいけば、問題は、今では明らかです - ときbar(0)が返され、valが再び1になるため、bar(1)のループが再び実行されます。

あなたおそらくはifでwhileを置き換えたい - このようにval`は、ループ内で変更されません `ので、実行の順序は

bar(3): if (3 > 0) { x = x + bar(2); } 
    bar(2): if (2 > 0) { x = x + bar(1); } 
    bar(1): if (1 > 0) { x = x + bar(0); } 
     bar(0): return 0; 
    bar(1): return 1; 
    bar(2): return 2; 
bar(3): return 3; 

Answer 2

あなたは私が多くを学ぶためにこの簡単な質問を展開したいループ

x= x + bar(--val); 

Answer 3

内valを更新する必要があります。投票して、それ以上のものを追加しないでください。

printf()を追加して、作成する機能のスタックを表示します。

int y=0; 
int bar(int val) { 
    int x = 0; 
    printf("val-before: %d\n", val); 
    while(val > 0) { 
     x= x + bar(val-1); 
     printf("val-inside: %d\n", val); 
    } 
    y++; 

    printf("bar(): %d finished\n", y); 

    return val; 
} 

は端からいくつかの出力

bar(3); 

それを呼び出す：

bar(): 7528 finished 
val-inside: 1 
val-before: 0 
bar(): 7529 finished 
val-inside: 1 
val-before: 0 
bar(): 7530 finished 
val-inside: 1 
val-before: 0 
bar(): 7531 finished 
val-inside: 1 
val-before: 0 
bar(): 7532 finished 
val-inside: 1 

この変更は、8の機能を生み出します。

haccksたちはx= x + bar(--val); while内部のブレーク無限の関数呼び出し

を変更し、この出力を生成する場合は言ったように：

val-before: 3 
val-before: 2 
val-before: 1 
val-before: 0 
bar(): 1 finished 
val-inside: 0 
bar(): 2 finished 
val-inside: 1 
val-before: 0 
bar(): 3 finished 
val-inside: 0 
bar(): 4 finished 
val-inside: 2 
val-before: 1 
val-before: 0 
bar(): 5 finished 
val-inside: 0 
bar(): 6 finished 
val-inside: 1 
val-before: 0 
bar(): 7 finished 
val-inside: 0 
bar(): 8 finished 

Answer 4

コード化されたとして、あなたが実際に複数の無限ループと再帰呼び出しごとに1つずつ持っていますvalがループ内で更新されていないため、val > 0です。もちろん、実際に実行されているのは唯一のもので、最後のものはval = 1です。を返し続けます。0を返します。したがって、xも増分されません。

あなたは、ループ内valをデクリメントしたい、とあなたはおそらく1にxを初期化し、xの代わりvalを返すようにしたいです。

#include <stdio.h> 
#include <stdlib.h> 

int bar(int val) { 
    int x = 1; 
    while (val > 0) { 
     x += bar(--val); 
    } 
    return x; 
} 

int main(int argc, char *argv[]) { 
    if (argc > 1) { 
     for (int i = 1; i < argc; i++) { 
      int v = atoi(argv[i]); 
      printf("bar(%d) = %d\n", v, bar(v)); 
     } 
    } else { 
     for (int i = 0; i < 20; i++) { 
      printf("bar(%d) = %d\n", i, bar(i)); 
     } 
    } 
    return 0; 
} 

出力：

bar(0) = 1 
bar(1) = 2 
bar(2) = 4 
bar(3) = 8 
bar(4) = 16 
bar(5) = 32 
bar(6) = 64 
bar(7) = 128 
bar(8) = 256 
bar(9) = 512 
bar(10) = 1024 
bar(11) = 2048 
bar(12) = 4096 
bar(13) = 8192 
bar(14) = 16384 
bar(15) = 32768 
bar(16) = 65536 
bar(17) = 131072 
bar(18) = 262144 
bar(19) = 524288 

2の力を計算するための複雑な、時間のかかる、意外な方法

はこれを試してみてください。

• 空間の複雑さO（n）再帰呼び出しのためです。
• 時間複雑O（2 ^N）がコンパイルされ、言語を解釈ベンチマークの良い候補作る：bar(30)（clang -O2）私のラップトップ上で、ほぼ3秒かかります。