遞歸問：修訂

Question

我的幻燈片說：

• 遞歸調用應該永遠是比當前的

• 必須有一個非遞歸如果數據結構選擇一個較小的數據結構太小

• 您需要的包裝方法，使訪問的遞歸方法

只需從幻燈片中閱讀這些內容是沒有意義的，尤其是看到它是聖誕節前的話題！

任何人都可以嘗試清理它意味着什麼嗎？

謝謝

Answer 1

一個recurssive調用應始終在一個較小的數據結構比當前

一般來說，這是不正確的，但如果你是在談論鏈表與操縱它是遞歸的。這意味着你需要始終努力尋求一種解決方案，而這通常是處理比你開始時更小的問題。

以Quicksort爲例。每次調用該函數時，都會使用一組較小的數據。

以另一個打印鏈表的例子，下一次你調用遞歸函數時，參數應該是鏈表的尾部（這段代碼有一個錯誤，但是這導致我們到下一個點）

void printList(List l){ 
    print(l.head); 
    printList(l.tail); 
} 

必須有一個非recurssive選項，如果所述數據結構是太小

這意味着應該有一個基本情況。函數停止再次調用自己的點。

int factorial(int n){ 
    if (n == 1){ //the base case is when n = 1 
     return 1; 
    } 
    return n*factorial(n-1); 
} 

讓我們回到打印鏈表的例子，必須有，你只剩下一個空列表（在這種情況下，函數應該什麼都不做）的情況下。讓我們再回到代碼打印鏈表

void printList(List l){ 
    if (l.empty == true){ //the base case is when the list l is empty 
     return; 
    } 

    print(l.head); 
    printList(l.tail); 
} 

您需要的包裝方法，使訪問的recurssive方法

我不知道Java的，它是不是一個真正的語言是爲遞歸設計的，但是在許多情況下，遞歸函數的參數比使用API​​的人應該能夠看到的參數多。例如，你可能想在那裏有一個櫃檯。

你可以有一個包裝函數，它可以簡化參數，只是需要什麼。包裝函數然後調用真正的工作者函數。

一個例子可能是如果我們有一個鏈表類，它具有遞歸函數來打印列表。使用API​​它並沒有太大的SENCE

void printList(List l); 

然而，因爲它是一個類的方法，就有人來要做到這一點：它的聲明會是這個樣子

myList.printList(myList); 

所以一可以創建包裝函數，該函數沒有任何參數，然後調用完成該工作的代碼。

void printList(){ 
    doPrintList(this); //pass in the List object as the first argument 
} 

然後，所有使用API​​的程序員所要做的就是：

myList.printList();