該遞歸函數是如何工作的？

可能是一個非常基本的問題，但我只是被困住了。我試圖運行以下遞歸函數：該遞歸函數是如何工作的？

//If a is 0 then return b, if b is 0 then return a, 
    //otherwise return myRec(a/2, 2*b) + myRec(2*a, b/2)

但它只是陷入無限循環。任何人都可以幫助我運行該代碼並解釋該函數的工作原理嗎？我沒有任何問題地構建了各種遞歸函數，但是這只是在我的腦海裏鑽了一個洞。謝謝。

這裏是我試圖做的：

#include<iostream> 

int myRec(int a, int b){ 

    if (a==0){ 
     return b; 
    } 

    if (b==0){ 
     return a; 
    } 
    else return myRec(a/2, 2*b) + myRec(2*a, b/2); 
} 

int main() 
{ 

    if (46 == myRec(100, 100)) { 
     std::cout << "It works!"; 
    } 
}

來源

2014-04-28 Pasha

你爲什麼期待46？ –

永不停止，因爲零永遠不會到達。可能是你應該停止，當它小於1. – PatricK

46是答案。我只知道它。 – Pasha

我認爲你缺少某些情況下的邏輯。我在C年代的最後一個程序，所以如果錯誤的話糾正我的語法。假設低於1的數字將被轉換爲自動歸零......

#include<iostream> 

int myRec(int a, int b){ 
    // Recurse only if both a and b are not zero 
    if (a!=0 && b!=0) { 
     return myRec(a/2, 2*b) + myRec(2*a, b/2); 
    } 
    // Otherwise check for any zero for a or b. 
    else { 
     if (a==0){ 
      return b; 
     } 
     if (b==0){ 
      return a; 
     } 
    } 
}

UPDATE：

我都差點忘了Ç如何作用於回報 ...

int myRec(int a, int b){ 
    if (a==0){ 
     return b; 
    } 
    if (b==0){ 
     return a; 
    } 
    return myRec(a/2, 2*b) + myRec(2*a, b/2); 
}

VBA當量與一些變化，用於顯示可變狀態

Private Function myRec(a As Integer, b As Integer, s As String) As Integer 
    Debug.Print s & vbTab & a & vbTab & b 
    If a = 0 Then 
     myRec = b 
    End If 
    If b = 0 Then 
     myRec = a 
    End If 
    If a <> 0 And b <> 0 Then 
     myRec = myRec(a/2, 2 * b, s & "L") + myRec(2 * a, b/2, s & "R") 
    End If 
End Function 

Sub test() 
    Debug.Print myRec(100, 100, "T") 
End Sub

運行在Excel中測試給出了該（它的一小部分，因爲它overstacks Excel）中：

T: Top | L: Left branch in myRec | R: Right branch in myRec

ImmediateOutput

根本原因將是返回的總和，其觸發更多的遞歸調用。

重複一個和從遞歸樹的2級各支路B原始值的...

diagram

來源

2014-04-28 01:34:59 PatricK

謝謝。 Btu我認爲它幾乎完成了我最初的代碼。它仍然陷入無限循環並崩潰。 – Pasha

不，它不會與'if（b == 0）{'一起使用。您可以改爲刪除原始帖子中的「else」。 – PatricK

但是，這是完全一樣的，我的原代碼。它崩潰了，否則我不會問這個問題。 – Pasha

好了，讓我們精神上跟蹤它一下：

Starting with a, b (a >= 2 and b >= 2) 
myRec(a/2, 2*b) + something 
something + myRec(2*a', b'/2)

替換爲/ 2的」和2 *用於B '，我們得到myRec(2*(a/2), (b*2)/2)，這正是我們開始的地方。

因此，我們永遠不會得到任何地方。

（請注意，我在這裏省略了一些舍入，但您應該很容易地看到，通過這種舍入，您只能將a舍入爲最接近的偶數，此時它將永遠在該數字和一半數量）

來源

2014-04-28 01:03:10

所以MyRec（2,2）= MyRec（1,4）+ MyRec（4,1）
而MyRec（1,4）= MyRec（.5,8）+ MyRec （2,2）
所以MyRec（2,2）= MyRec（.5,8）+ MyRec（2,2） + MyRec（4,1）
哎呀。

（.5的實際上是零，但是這並不重要。關鍵是，該功能將不會終止對大範圍的可能的輸入。）

來源

2014-04-28 01:06:56

（'1/2'爲零。） – aschepler

我會添加一個註釋，它並不重要。 –

擴展在gha.st的回答，將函數的返回值視爲表達式的總和，而不必擔心任何代碼。

首先，我們先從myRec（A，B）。我們只是把它表示爲（a，b），以便於閱讀。

正如我每一行下去，每一個表達式是等效，無視的情況下A = 0或B = 0。（a，b）= （a/2,2b）+（2a，b/2）= （a/4,4b）+（a，b）+（a，b）+（4a ，b/4）

現在，我們看到，在表達非終止點，計算（A，b）首先需要計算（A，b）。對這樣的問題

遞歸工作，因爲參數一般朝着「基本情況」，在該遞歸停止趨向。一個很好的例子是排序列表;你可以遞歸地對列表的一半進行排序，直到給出的輸入列表具有< = 2個元素，這沒有遞歸是微不足道的。這稱爲mergesort。

但是，你myRec功能不具備基本情況，因爲對於非零a或b，相同的參數必須傳遞到在某些點的功能。這就像試圖對列表進行排序，其中列表的一半具有與整個列表一樣多的元素。

來源

2014-04-28 01:16:41 millinon

嘗試用替換遞歸調用：

返回myRec（a/2，b/3）+ myRec（a/3，b/2）;

來源

2014-04-30 14:06:44

該遞歸函數是如何工作的？

回答

相關問題