c - このコードで実際に何が起こっているのでしょうか？

Question

再帰関数を含むコードがあります。私は再帰に多くの時間を浪費しましたが、それでも実際にはそれを得ることができませんでした：

#include<stdio.h>
void count(int);

int main()
{
    int x=10,z;
    count(x);
}

void count(int m)
{
    if(m>0)
        count(m-1);
    printf("%d",m);
}

1回目countが引数10で呼び出されると、条件が満たされ、ここで再帰部分が開始されます。関数がそれ自体を呼び出すと、実際に何が起こりますか？理解できません。スタックを参考に説明してください。

score 31 · Accepted Answer

mが 0 より大きい間、を呼び出しますcount。スタック呼び出しの表現は次のとおりです。

 count (m = 10)  
   count (m = 9)  
     count (m = 8)  
       count (m = 7)  
         count (m = 6)    
           count (m = 5)     
             count (m = 4)     
               count (m = 3)     
                 count (m = 2)     
                   count (m = 1)
                     count (m = 0)
                     printf 0
                   printf 1
                 printf 2
               printf 3
             printf 4
           printf 5
         printf 6
       printf 7
     printf 8
   printf 9
 printf 10

score 2 · Accepted Answer

次に自分自身を呼び出すときは、値が小さくなります

count(int m)
{
 if(m>0)
 count(m-1); // now it is calling the method "count" again, except m is one less
 printf("%d",m);
}

したがって、最初に 10 で count を呼び出し、次に 9、次に 8、次に 7 と呼び出します。この if ステートメントが true でなくなるまでずっと:

if(m>0)

混乱を招く可能性があるのは、if ステートメントが次の行にのみ適用されることです (printf は if ステートメントの一部ではありません)。

だからあなたは持っています：

count(int m)
    {
     if(m>0)
     {
         count(m-1); // now it is calling the method "count" again, except m is one less
     }
     printf("%d",m);
    }

そのため、m が > 0 でなくなると再帰呼び出しが停止し、printf が呼び出されます。

m が 0 の場合に printf を呼び出した後、その 'count' 呼び出しから戻り (m が 1 に等しい場所に戻る)、m が 1 の場合に printf を呼び出し、次に m が 2 の場合に printf を呼び出します。、 .....

したがって、出力は次のようになります。

"0 1 2 3 4 5 6 7 8 9 10"

編集:スタックに関して:

これは、スタックが行っていることです:

count(10) // push count(10)

->

count(9) // push count(9)
count (10)

->

...

->

count(0) // push count(0)
count(1)
count(2)
count(3)
count(4)
count(5)
count(6)
count(7)
count(8)
count(9)
count(10)

-> (そして、印刷を開始し、スタックからメソッドをポップします)

// pop count(0), and printf(0)
count(1)
count(2)
count(3)
count(4)
count(5)
count(6)
count(7)
count(8)
count(9)
count(10)

->

// pop count(1), and printf(1)
count(2)
count(3)
count(4)
count(5)
count(6)
count(7)
count(8)
count(9)
count(10)

->

...

->

// pop count(9), and printf(9)
count(10)

->

// pop count(10), and printf(10)

score 0 · Accepted Answer

If you want a more specific answer, then you have to look into how compilers work. But generally speaking the compiler will create machine code for the function that includes a preamble, in this code enough memory is allocated on the stack (by decrementing a stack pointer) that a copy of the functions variables can be placed on the stack (we can store the state of the function).

The function will have values stored in registers and memory and these must be stored on the stack for each (recursive) call, otherwise the new call will overwrite the precious data!. So very basically the machine code looks like this (pseudo code)

//store m on the stack 
store m,stack_pntr+m_offset
//put input values in designated register
a0 = m
//allocate memory on the stack
stackPntr -= stack_size_of(count_vars)
//store return address in allocated register
//jump to the first instruction of count
.
.

By changing some data used for computation we can go back and read the same instructions again and get a different result. The abstraction of recursive function allows us to manipulate the data we want to change in a nice "call by value" way so that we don't overwrite it unintentionally.

This is done by the compiler when it stores the state of the calling function on the stack so we don't have to manually store it.

score 0 · Accepted Answer

関数が呼び出されると、(次に実行するコードの) 戻りアドレスが現在の引数と共にスタックに格納されます。関数が終了すると、アドレスと引数がポップされるため、CPU はどこでコードの実行を継続するかを認識します。

関数のアドレスを書きましょう (この例の目的のみ)

count(int m)
{
(address = 100)  if(m>0)
(address = 101)     count(m-1); // now it is calling the method "count" again, except m is one less
(address = 102)  printf("%d",m);
}

m = 1 の場合:

はフルフィールドなので、 with でifコードを実行します。とがスタックにプッシュされ、関数がwithから再度実行されます。実行してコンソールに 0を出力するので。関数が終了し、最後の戻り値と引数がポップされ、行が実行されて画面に 1 が出力されます。address 101m = 1address 102m = 1address 100m = 0m = 0address 102address (102)m = 1address 102

score 0 · Accepted Answer

関数countはの整数引数で呼び出されます10。
関数の引数mは10よりも大きいため、に等しいマイナスの整数引数を使用して関数自体を呼び出し0ます。countm1019
ステップ 2 は、が以下の値になる(m-1)までさまざまな引数を使用して繰り返され、その時点でプログラムはの値を出力します。m0m

再帰関数は、与えられたパラメーターを変更し、目的の結果が返されるまで (この場合mはより大きくない0)、その変更された値で自分自身を呼び出します。

score 0 · Accepted Answer

各番号は行番号を表します。

#include<stdio.h>
count(int);
main()
{
1int x=10,z;
2count(x);
}  
count(int m)
{
3if(m>0)
4   count(m-1);
5printf("%d",m);
}

実行は次のように行われます (x=3 の場合) -

行番号|x の値

1 3

2 3

3 3

4 2

3 2

4 1

3 1

4 0

5 0

5 1

5 2

5 3

画面に表示される数字 0 1 2 3

c - このコードで実際に何が起こっているのでしょうか？

6 に答える 6

Related

Reference