递归函数的返回值

下面的程序的输出是24.但我无法理解函数f1（参数）的行为。递归函数的返回值

m1 nad m2有一个递归的f1调用。考虑m1和m2保存函数f1的堆栈。 M1堆栈将包含：

1]0,12,a 2]0,6,a 3]0,3,a 4]0,1,a 5]0,0,a

和M2堆栈将包含：

1]13,12,a 2]20,6,a 3]24,3,a 4]26,1,a 5]27,0,a

什么M1和M2值不放？请解释递归函数的这种行为。

#include <stdio.h> 
main() 
{ 
int i, n, m, b, x[25]; 
int f1(int, int, int j[25]); 
for(i=0;i<25;i++) x[i] = i; 
i=0; m = 24; 
b=f1(i, m, x); 
printf("res %d\n",b); 
} 

int f1(int p, int q, int a[25]) 
{ 
int m1,m2; 
if (q==0) 
    return(a[p]); 
else 
{ 
    m1 = f1 (p, q/2, a); 
    m2 = f1(p+q/2+1,q/2,a); 
    if(m1<m2) 
    return (m2); 
    else 
    return(m1); 
} 
}

来源

2011-08-15 Angus

这是功课吗？ – jv42

这看起来有点类似于QSort不是吗？ – jv42

@ jv42：不，这不是一个家庭作业。我不明白这是如何输出24. – Angus

那么，有两点需要理解代码：

揭开可怕C的堆和
理解递归函数本身之间的实际的算法。

试图理解这些代码的时候什么东西帮助我是：

清理C代码。在这种情况下，它的意思是：
1. 精神上跟踪初始化和重写来静态初始化，所以你看到的值如下所示：
  
  INT X [25] = {0，1，2，3 ，4，5，6，7，8，9，10，11，12， 13,14,15,16,17,18,19,20,21,22,23,24};
2. 将无用的任务分配给i和x，这样您就可以看到最初的呼叫。
将函数重写为数学符号，伪代码甚至人类语言。
```
f(p, q, array) = larger of f(p, q/2, array) and f(p+q/2+1, q/2, array) 
```
如果您在使用人类语言继续得远一点，你会清楚地看到什么是应该做。

现在我说“应该这样做”是故意的。 (p, q/2)和(p+q/2+1, q/2)看起来像第一个和第二个一半......除非他们不是。

该代码应该返回24，但它是完全错误的，在问题中引用的堆栈实际上证明了它。 m2堆栈包含最后一点“f1（27，0，a）”，该调用将执行一个[27]，但该数组只有25个元素！（纯粹的机会上面的内存可能是0初始化的，所以它确实返回了24，但是如果它是由一些调试模式初始化的（我已经看到0xdeadbeef，0xa5a5a5a5和0xcccccccc），它会返回）。

在C中，它是有意设计的（并且C++在其他地方使用它们）最容易使用半开区间。 [start，one-past-end）或者start + length，它们很好地相互转换。然而，这里函数获取（开始，长度为1），并在内部不一致地对待它。

作为一名学生，你必须能够理解这样的代码，因为你会遇到很多蹩脚的不可读的bug代码，只能在野外偶然使用。但是，如果你提出这样的事情，你会正确地通过考试。

来源

2011-08-15 08:45:29

在这里你想不到的M1栈和M2堆栈非终止在M1调用F1结果和M2递归调用。

要分析发生了什么事情，尝试一个小的p和q值。

f1(0, 1, a) 
     m1 = f1(0, 0, a); /* q/2 == 1/2 == 0 */ 
      /* q now 0 so return a[0] */ 
     m2 = f1(1, 0, a); 
      /* q now 0 so return a[1] */ 

    overall result the larger of a[0] and a[1].

现在尝试它为f1（0,2，a）等，直到你看到发生了什么。

来源

2011-08-15 07:33:47 djna

递归函数的返回值

回答

相关问题