消除所選擇的尾遞歸排序

Question

代碼：（我試圖轉換到Java它在，我不知道不同的語言）：

selection_sort(int a, int b){ 
    if(a == b+1){ 
     //do nothing 
    }else{ 
     i = minIndex(arr, a, b); //minIndex finds minimum value of 2 index's an array 
     if(i != a) 
      swap(arr, i, a); 
     selection_sort(a+1, b); 
    } 
} 

家庭作業問題要求以消除此代碼尾遞歸。這是否意味着用迭代循環替換最後一個遞歸調用？或者添加額外的遞歸調用？

我認爲這個問題可能源於我不知道規則遞歸和尾遞歸算法之間的區別。如果我錯了，請糾正我的錯誤，但我的理解是，尾遞歸用於通過減少遞歸調用的數量來提高效率，除非調用將是代碼中的最後一條指令。重要的是，遞歸調用的次數少意味着遞歸堆棧要存儲在內存中。

編輯：修復代碼中的交換呼叫錯誤。

Answer 1

基本上，尾遞歸是你有一個函數自己調用時，但不需要做任何事情之後，除了可能返回遞歸調用的結果。這是遞歸的一種特殊情況......不是它的工作原理，而是事實上很容易變成循環。對於不優化尾遞歸的編譯器/解釋器，這可能意味着正確工作和溢出調用堆棧之間的區別。

例如：

void countdown(int t) { 
    if (t <= 1) return; 
    printf("%d\n", t); 
    countdown(t - 1); 
} 

這是尾遞歸，因爲沒有什麼需要後countdown調用自身的情況發生。

對比的東西，如

int factorial(int n) { 
    if (n <= 1) return 1; 
    return n * factorial(n - 1); 
} 

這是不尾遞歸。區別在於函數在調用自身之後需要重新獲得控制權，所以它可以將結果乘以n。

（附加點雖然：你可以用一個叫做continuation-passing style的技術把它變成一個尾遞歸函數，基本上，在這種情況下，你可以將結果和其他參數一起傳遞。

int factorial(int n, int product = 1) { 
    if (n <= 1) return product; 
    return factorial(n - 1, product * n); 
} 

但我離題了。

無論如何，刪除尾遞歸的編譯器基本上只是調整當前的調用框架，以便變量是它們對於調用的內容，然後跳回到函數的開頭。你的老師可能不會那麼喜歡，原因很多。但我們從那裏開始。

selection_sort(int a, int b){ 
    tail_call: 
    if(a == b+1){ 
     //do nothing 
    }else{ 
     i = minIndex(arr, a, b); 
     if(i != a) 
      swap(arr, i, a); 

     // tweak the variables so the next iteration sees (a+1, b) 
     a += 1; 
     goto tail_call; 
    } 
} 

雖然我們正在重新編排東西，但空白條件塊相當可怕。這也可以改寫爲

selection_sort(int a, int b){ 
    tail_call: 
    if(a != b+1){ 
     i = minIndex(arr, a, b); 
     if(i != a) 
      swap(arr, i, a); 

     // tweak the variables so the next iteration sees (a+1, b) 
     a += 1; 

     goto tail_call; 
    } 
} 

現在，你可能已經被告知，goto是魔鬼。 :)（這被誇大了，但它不應該用在有更好的選擇的地方。）所以重構來擺脫它。

我們如何擺脫它？我們找到一個控制結構來完成goto試圖做的事情。在這種情況下，while循環很適合這個法案。在condition缺席範圍的差異，此代碼：

loop: 
    if (condition) { 
     ...magic... 
     goto loop; 
    } 

不完全一樣的東西就象這樣：

while (condition) { 
    ...magic... 
} 

的地步，許多編譯器甚至會產生兩個完全相同的代碼。

所以讓我們用while循環清理代碼。

selection_sort(int a, int b){ 
    while (a != b+1) { 
     int i = minIndex(arr, a, b); 
     if(i != a) 
      swap(arr, i, a); 

     a += 1; 
    } 
} 

Answer 2

你可以看到這裏尾遞歸What is tail recursion?，What is tail-recursion elimination?，你可以試試這個代碼，我沒有測試過，只是這個想法

selection_sort(){ 
    int firstIndex = 0; 
    int lastIndex = arr.length; 
    while(firstIndex < lastIndex) { 
     int i = minIndex(arr, firstIndex, lastIndex); 
     if(i != a) { 
      swap(entries, i, firstIndex); 
     } 
     firstIndex ++; 
    } 
} 

因爲你可以在尾遞歸版本中看到，它只是更新一，所以我們可以嘗試while循環