遞歸函數的返回值

下面的程序的輸出是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

遞歸函數的返回值

回答

相關問題