2 
#include <stdio.h>

void call(int n )
{
    if ( n > 0 )
    {
        call(--n) ;
        printf("\n%d",n) ;
        call(--n) ;
    }
}

int main(void )
{
    int a = 3 ;
    call(a) ;
    return 0 ;
}

上記のコードでは、その背後にあるロジックを理解するのが困難です。出力として 0 1 2 0 を取得しています。なんで？

4

3 に答える 3

5 
call(3)
│ n3=3
│ --n3 (n3=2)
├╴call(2)
│ │ n2=2
│ │ --n2 (n2=1)
│ ├╴call(1)
│ │ │ n1=1
│ │ │ --n1 (n1=0)
│ │ ├╴call(0)
│ │ │ └ return
│ │ │
│ │ │ printf("\n0");           ⇦ 0
│ │ │
│ │ │ --n1 (n1=-1)
│ │ ├╴call(-1)
│ │ │ └ return
│ │ └ return
│ │
│ │ printf("\n1")              ⇦ 1
│ │
│ │ --n2 (n2=0)
│ ├╴call(0)
│ │ └ return
│ └ return
│
│ printf("\n2");               ⇦ 2
│
│ --n3 (n3=1)
├╴call(1)
│ │ n1=1
│ │ --n1 (n2=0)
│ ├╴call(0)
│ │ └ return
│ │
│ │ printf("\n0");             ⇦ 0
│ │
│ │ --n1 (n1=-1)
│ ├╴call(-1)
│ │ └ return
│ └ return
└ return
于 2012-12-15T08:13:15.020 に答える
5

まず、基本ケースを見つけますcall(n), when n<=0。何もせず、単に戻ります。

定義の一般的なケースではcode(n)、「デクリメントnと再帰 (ずっと下まで)。コントロールが戻ると、出力n(その値は保持されます) し、再度デクリメントして再帰します」。

または、方程式を使用します。

call(n) | when(n<=0) = NO-OP
call(n) | otherwise  = call(n-1), print(n-1), call(n-2)

そう、

call(1) = call(0), print(0), call(-1)
        = print(0)

call(2) = call(1), print(1), call(0)
        = print(0), print(1)

call(3) = call(2), print(2), call(1)
        = (print(0), print(1)), print(2), print(0)

続けて、

call(4) = 0120+3+01
call(5) = 0120301+4+0120
call(6) = 012030140120+5+0120301
....

最新の 2 つの値だけを維持しながら、結果として得られる出力の不定のシーケンスを生成できるようです。

(n,a,b) --> (n+1,b,b+n+a)

したがって、ベースケースに向かって下に再帰する代わりに、これは開始ケースから離れたコアカージョン(2,0,1)を記述します(1ケースは特別な事実によってカバーされ(1,_,0)ます)。実際の無限に成長する (つまり「無限」 ) シーケンスとしてコーディングすることも、それから無限ループを作成することもできます。

そのような非終了計算の目的は何でしょうか? 結果の計算を説明するには、一般的に. しかしもちろん、 の目標値に到達すると、そのような計算を簡単に省略できますn。

利益？再帰の代わりに、反復ループが得られます!

output(1) = "0"
output(n) | when(n>1) = 
   let {i = 2, a="0", b="1"}
   while( i<n ):
      i,a,b = (i+1),b,(b+"i"+a)
   return b
于 2012-12-15T08:28:58.180 に答える
1

コード フローを理解しようとするとき、頭を包むことができません。単純な戦略を使用します。

出力を詳細に記録します。たとえば、呼び出し関数に単純な printf ステートメントを含める代わりに、アプリケーションのフローをマップできます。これが例です

#include <stdio.h>

void call(int n, int depth)
{
    printf("%.*s(enter) n is (%d)\n", ++depth, "-----", n);
    if ( n > 0 )
    {
        call(--n, depth) ;

        call(--n, depth) ;
    }
    printf("%.*s(exit) n is (%d)\n", depth--, "-----", n);
}

int main(void )
{

    int a = 3 ;

    call(a, 0) ;
    getchar();
    return 0 ;
}

これにより、次のようになります。

-(enter) n is (3)
--(enter) n is (2)
---(enter) n is (1)
----(enter) n is (0)
----(exit) n is (0)
----(enter) n is (-1)
----(exit) n is (-1)
---(exit) n is (-1)
---(enter) n is (0)
---(exit) n is (0)
--(exit) n is (0)
--(enter) n is (1)
---(enter) n is (0)
---(exit) n is (0)
---(enter) n is (-1)
---(exit) n is (-1)
--(exit) n is (-1)
-(exit) n is (1)
于 2012-12-15T09:13:39.713 に答える