如何使用遞歸技術來檢查值X是列表成員L

Question

我不擅長遞歸編程。我認爲這個問題很簡單，但我不知道如何解決它。我需要一些想法如何編碼。請幫幫我！

如何使用遞歸技術檢查值X是列表L的成員？

Answer 1

非常粗糙的僞代碼，但它會是這樣的。

int checkList(List L, Value X, int current_index) 
{ 
    if (List.ValueAt(current_index) == X) 
    { 
     return 1; 
    } 

    if (List.Length == current_index+1) 
    { 
     return 0; 
    } 

    return checkList(L, X, current_index+1); 
} 

爲什麼它需要是遞歸的呢？迭代執行迭代要好得多，就像遞歸一樣，每個函數調用都需要添加到內存棧以獲取返回信息。

Answer 2

爲了解決使用遞歸的任何問題，你只需要思考「如果我知道更小的值的答案如何回答我的問題的一些變量X」的方式？ - 在你的情況 - 「如果我已經知道X是否爲列表K的成員，那麼它是否爲列表L的成員，我該如何測試值X是否爲列表K的成員，即列表尾部（列表中的所有元素，但第一個元素） L·」

作爲一個例子，考慮不同的事情 - 如何獲得使用遞歸整數列表的最大值？

1. 一個元素列表的最大價值是它的唯一元素，所以MAX([ x ]) = x
2. 如果我知道最大的名單的K後來我知道，最大的K和新的x值組成的列表僅僅是他們更大，所以MAX([ x | K ]) = x if x > MAX(K) or MAX(K) otherwise。在哪裏|是連接操作，所以[1 2 3] = [1 | [2 3]

執行期間

現在，這樣的遞歸將採取列表的第一個元素，並將其與其他部分的最大比較和遞歸調用本身，直到它找到一個名單 - 爲其最大的是易於定義。現在，您可以用相同的方式找到問題的解決方案。