回溯遞歸調用

Question

我是新的遞歸，並試圖瞭解它是如何工作的，並試圖追蹤它如何接近找到答案。下面的代碼發現了整數數組中搜索到的數字的最後一個索引，例如in[4]={1,2,3,2}，並且該陣列中搜索到的數字是2。 這個問題的答案是3，因爲它是最後一個索引。現在我將嘗試寫這個代碼如何去做。in[]是輸入數組，stin是起始整數，要找到的數字是num。

1. 在線路INT ANS lastIndex的（在，STIN + 1，大小，NUM）的函數遞歸調用到這是當它的尺寸變STIN == siz.then其值被返回到它的基本情況函數調用它。我的問題是這個函數如何在遞歸語句後到達這一行。請提供此代碼的解釋。

   int lindex(int in[], int stin, int num){ int size=strlen(in); if(stin == size){ return -1; } int ans = lastIndex(in, stin + 1, num); if(ans != -1){ return ans; }else{ if(in[stin] == num){ return stin; }else{ return -1; } } }

Answer 1

實施，將通過從返回到達遞歸調用之後的行。如果對遞歸不熟悉，可能需要一些時間來適應它。如果您能夠使用調試器，我強烈建議您嘗試一下並檢查調用堆棧和局部變量值。但是，遞歸調用的順序可以按照以下方式進行擴展，使用示例，使用插入值的僞循環符號。

1. call lindex({1,2,3,4}, 0, 2): 
    int size=strlen(in); // assigns 4 
    if(0 == 4){   // condition is false 
    } 
    int ans = lastIndex({1,2,3,4}, 1, 2); // assigns 3, as we see below 
    if(3 != -1){   // condition is true 
     return 3; 
    } 

2. call lindex({1,2,3,4}, 1, 2): 
    int size=strlen(in); // assigns 4 
    if(1 == 4){   // condition is false 
    } 
    int ans = lastIndex({1,2,3,4}, 2, 2); // assigns 3, as we see below 
    if(3 != -1){   // condition is true 
     return 3; 
    } 

3. call lindex({1,2,3,4}, 2, 2): 
    int size=strlen(in); // assigns 4 
    if(2 == 4){   // condition is false 
    } 
    int ans = lastIndex({1,2,3,4}, 3, 2); // assigns 3, as we see below 
    if(3 != -1){   // condition is true 
     return 3; 
    } 

4. call lindex({1,2,3,4}, 3, 2): 
    int size=strlen(in); // assigns 4 
    if(3 == 4){   // condition is false 
    } 
    int ans = lastIndex({1,2,3,4}, 4, 2); // assigns -1, as we see below 
    if(-1 != -1){   // condition is false 
    }else{ 
     if(in[3] == 2){ // condition is true 
     return 3; 
    } 

5. call lindex({1,2,3,4}, 4, 2): 
    int size=strlen(in); // assigns 4 
    if(4 == 4){   // condition is true 
     return -1; 
    } 

如果我們討論各個步驟的語義，則實現變得更易於訪問。首先，檢查起始索引點是否是數組，在這種情況下，找不到所需的數字，返回-1。否則，我們會在數組的尾部尋找數字。如果可以在那裏找到，我們返回在遞歸調用中找到的索引。否則，我們測試當前位置是否與想要找到的數相等，因爲它不會出現在數組的尾部。總之，這將返回搜索號碼最右邊的索引（如果它包含的話）。

通過從遞歸調用返回的'後退'通過調用堆棧完成;每個遞歸調用都有自己的一組局部變量。