C递归问题

Question

我有一个关于递归函数的查询。这是我的节目。

#include <stdio.h>

int fun(int);

int main(void)
{
    int x;
    int k=3;
    x = fun(k);
    printf("%d\n",x);
    return 0;
}

int fun(int a)
{
    int f;
    if(a == 1) return (1);
    f = 2 + fun(a-1);
    return (f);
}

其中有一个值K=3 (在STEP-6中)。在STEP-7中，函数fun(k)将K的值传递给STEP-11 int fun(int a)中被调用的函数。在被调用的函数中，fun(int a)递归发生了2次，即(3,2)使得a=1的值。在STEP-14中，f的值变为3，因为f=2+ (fun(1)=1)。在STEP-16中，它返回到被调用的函数即fun(int a)=3。它应该打印x is 3的值，但不太可能不是。它是x =5

Answer 1

让我们检查一下fun()的呼叫顺序，好吗？

的参数值为3，从main()开始

• x = fun(3)
  • f = 2 + fun(2);
    • f = 2 + fun(1);

​

​

现在，让我们以相反的顺序检查返回值。

1. 最后一个调用，fun(1)返回1，
2. 第二个调用，fun(2)，返回2 + 1或3，
3. 最后一次调用，fun(3)返回2 + 3或5

这就是main()发出的电话。因此，在main()中，x获得5的值。

Answer 2

fun(3)的评估如下所示：

fun(3)
2 + fun(3-1)
2 + fun(2)
2 + 2 + fun(2-1)
2 + 2 + fun(1)
2 + 2 + 1
5

从您的描述中，我认为您对C中的作用域(和一般的递归)有一些误解。f被分配给fun(2)中的值3这一事实并不意味着fun(3)范围内的f值会发生变化--它们是完全独立的变量。

Answer 3

对于递归函数，绘制递归树以更好地可视化正在发生的事情通常是一个好主意。

• f(3)将调用f(2)，f(2)将进一步调用f(1)，这是基本情况。
• f( 1 )将返回1，现在f(2)将返回2+1= 3。
• f(3)将返回2+3= 5。

请查看下面的递归树：

     |------> returns (2 + 3) = 5
     |
    f(3)<---
     |     | 
     |     | returns (2 + 1)  = 3
    f(2)<---
     |     | returns 1
     |     |
    f(1)----
    (This is the base case. No further recursion. It returns 1).