在遞歸函數中返回函數和不返回有什麼區別？

我用C++寫了一個簡單的二進制搜索函數。代碼如下所示：在遞歸函數中返回函數和不返回有什麼區別？

int binary_search(int arr[], int key, int imin, int imax) 
{ 
    if (imin > imax) 
    { 
     return -1; 
    } 
    else 
    { 
     int imid = imin + (imax - imin)/2; 
     if (arr[imid] > key) binary_search(arr, key, imin, imid - 1); 
     else if (arr[imid] < key) binary_search(arr, key, imid + 1, imax); 
     else return imid; 
    } 

}

但我發現，如果我在第10行和11加return，代碼似乎以同樣的方式工作。代碼如下：

int binary_search(int arr[], int key, int imin, int imax) 
{ 
    if (imin > imax) 
    { 
     return -1; 
    } 
    else 
    { 
     int imid = imin + (imax - imin)/2; 
     if (arr[imid] > key) return binary_search(arr, key, imin, imid - 1); 
     else if (arr[imid] < key) return binary_search(arr, key, imid + 1, imax); 
     else return imid; 
    } 

}

所以我的問題是這兩種情況有什麼區別？

來源

2015-09-20 Xiang Zhang

打開更多編譯器警告。你應該得到一個關於達到非void函數的結尾。 – Biffen

您是否檢查過返回值的正確性？ –

任何不會返回任何內容的函數（void）在用完之前都必須遇到return聲明。這很簡單，因爲沒有魔法「如果我不返回某些東西就會返回X」，而且該人使用函數可能依賴於您承諾的回報（但未能交付）。

如果您現在按照導致原始函數中的遞歸調用的路徑，您將看到現在首先啓動遞歸調用的調用必須返回一些內容。相反，它簡單地忽略了遞歸調用的結果並且耗盡了要做的事情。

這導致了一種叫做未定義的行爲，因爲C++不知道你期望它做什麼。實際上，"it is legal for it to make demons fly out of your nose."雖然通常會脫離其靈魂的純仁 - 但卻限制了它的崩潰，可怕和不可預測。

兩個主要選項存在，爲什麼你沒有看到一個區別：

的代碼是這樣一種方式，如預期其不確定的煩躁將工作編譯。你必須不依賴於此，永遠。在實踐中，您的代碼將被編譯爲一個寄存器保存您的返回值（RAX）。由於遞歸調用是您的代碼最後一件事，因此該寄存器可能不會再次被修改，導致代碼執行，就好像您已經返回了遞歸調用的結果。

你的測試用例從來沒有真正做過遞歸調用。這在技術上是合法的，因爲程序的正確性取決於它在運行時的行爲。你應該也不依靠這個。

如果你有興趣，該標準的相關部分[stmt.return]/2，其中說：

[...]流下的函數到底是相當於到沒有價值的回報;這會導致值返回函數中的未定義行爲。

「流動」是指控制流程，「價值返回功能」是具有除void以外的返回類型的任何功能。

來源

2015-09-20 10:38:09

請注意，'main'是一個異常，並會返回'0'。 – Jarod42

@ Jarod42是的，但在另一種意義上它也是一個例外，因爲無論如何你可能不會調用'main'！ –

如果返回非void一個函數「落入端的」（即沒有返回語句）和呼叫者使用的返回值，則結果是不確定的行爲。這種情況發生在你的第一個版本中（無論是遞歸調用還是調用者），除非 - 偶然 - 你的測試用例只會導致執行return imid語句。

不幸的是，未定義行爲的一個可能結果是代碼似乎對所有測試用例都正常工作。沒有什麼可以阻止這一點。程序崩潰（或其他異常程序終止）是人們在未定義行爲發生時經常更熟悉的，但未定義行爲的更隱蔽的結果是代碼似乎的行爲就像沒有任何錯誤一樣。

在實踐中，您的第一個案例似乎正確工作的原因是盲目的運氣。由於歷史原因，我不會詳細介紹，一些公平的編譯器會將用於計算的工作數據（即函數中的語句）和結果放入機器寄存器中，不會打擾清除這些寄存器，並且（當函數返回int或其他非struct類型）使用那些相同的機器寄存器來保存函數的返回值。所以你可以很幸運，第一個例子中的代碼就像第二個代碼一樣。然而，問題在於標準沒有保證這種行爲，在編譯器之間可能會改變，可能會隨編譯器設置（例如優化選項）而改變，甚至在將來某個時候編譯器升級時甚至可能會改變。

來源

2015-09-20 10:49:48 Peter

遞歸最終將通過實際執行return語句結束。此時，編譯器會將返回值放在用於返回值的位置。

當你回到調用函數，不執行任何其他的返回語句，它恰好仍然存在。只是偶然。

來源

2015-09-20 10:58:53

在遞歸函數中返回函數和不返回有什麼區別？

回答

相關問題