c - 如何使用递归技术检查值 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 的成员，我如何测试值 X 是否是列表 L 的成员，这是列表 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] ]

现在在执行期间，这种递归将获取列表的第一个元素，并将其与其余元素中的最大元素进行比较，然后递归调用自身，直到找到单个列表 - 最大值很容易定义。现在你可以用同样的方法找到你的问题的解决方案。