如何使用递归技术来检查值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]

执行期间

现在，这样的递归将采取列表的第一个元素，并将其与其他部分的最大比较和递归调用本身，直到它找到一个名单 - 为其最大的是易于定义。现在，您可以用相同的方式找到问题的解决方案。