3

我有一个包含递归函数的代码。我在递归上浪费了很多时间，但我仍然无法真正理解：

#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);
}

当第一次count调用参数为 10 时，它满足条件，然后在这里开始递归部分。当函数调用自身时会发生什么？我不明白。请参考堆栈进行解释。

4

6 回答 6

31

Whilem大于 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
于 2012-09-04T14:26:05.383 回答
2

下次它调用自己时，它的值较小

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 语句不正确：

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 时，……

所以输出应该是：

"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)
于 2012-09-04T14:25:51.997 回答
0

当一个函数被调用时，返回地址（下一个要执行的代码）连同它的当前参数一起存储在堆栈中。一旦函数完成，地址和参数就会弹出，这样 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：

是全if域，所以我们在address 101with处执行代码m = 1。address 102并被推入堆栈，并从withm = 1再次执行该函数。因为我们在控制台上执行并打印 0。函数结束并弹出最后一个返回值和参数，并执行 at 行，在屏幕上打印 1。address 100m = 0m = 0address 102address (102)m = 1address 102

于 2012-09-04T14:31:56.563 回答
0
  1. count使用整数参数调用该函数10。
  2. 由于大于函数的函数参数调用自身，其整数参数m为负，等于。100countm1019
  3. 步骤 2 使用不同的参数重复，(m-1)直到m不大于0并且程序在该点打印 的值m。

递归函数只是修改给它的参数并使用修改后的值调用自身，直到返回所需的结果（在这种情况下m不大于0）。

于 2012-09-04T14:32:00.670 回答
0

每个数字指的是行号。

#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

于 2012-09-04T14:33:25.233 回答
0

如果你想要一个更具体的答案，那么你必须研究编译器是如何工作的。但一般来说，编译器会为包含前导码的函数创建机器代码，在此代码中，在堆栈上分配了足够的内存（通过递减堆栈指针），可以将函数变量的副本放在堆栈上（我们可以存储函数的状态）。

该函数的值将存储在寄存器和内存中，并且必须为每个（递归）调用将这些值存储在堆栈中，否则新调用将覆盖宝贵的数据！所以基本上机器代码看起来像这样（伪代码）

//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
.
.

通过更改一些用于计算的数据，我们可以返回并再次读取相同的指令并获得不同的结果。递归函数的抽象允许我们以一种很好的“按值调用”方式操作我们想要更改的数据，这样我们就不会无意中覆盖它。

这是由编译器在将调用函数的状态存储在堆栈上时完成的，因此我们不必手动存储它。

于 2012-09-10T07:55:19.897 回答