递归过滤不可变列表

Question

假设我有一个整数数组，我需要 return 一个包含所有可被 3 整除的数字的数组。

我得到了接口：

List<int> ListElementsDivisibleBy3Recursive(List<int> input)

所以它必须接受一个列表和return一个列表，并递归地过滤它。我试过从列表的开头弹出元素，直到我找到一个符合要求条件的数字，这就是我被卡住的地方。我不知道如何进入下一个元素并保留与条件匹配的元素。这是我目前所拥有的：

static List<int> ListElementsDivisibleBy3Recursive(List<int> input)
        {
            if (input.Count == 0)
                return input;
            else if (input.ElementAt(0) % 3 == 0)
            {
                return ListElementsDivisibleBy3Recursive(input); <--I have no idea what to do here
            }
            else
            {
                input.RemoveAt(0);
                return ListElementsDivisibleBy3Recursive(input);
            }
        }

如果允许我将指针传递到我所在的列表中的位置，那会容易得多，但我所拥有的只是输入列表和要使用的 return 列表。如何在保留与条件匹配的元素的同时删除列表中的元素？或者我是不是以错误的方式去做这件事？不确定我应该如何从逻辑上解决这个问题。我也意识到我的基础条件也不对。

Answer 1

return input.Where( i => (i % 3) == 0).ToList();

Answer 2

整个问题都很奇怪。

要解决初始问题，处理当前位置，您可以跟踪当前索引（在我的代码中称为 count 的变量中），然后做：

return currentList.AddRange(ListElementsDivisibleBy3Recursive(input.Skip(count).ToList()));

使用Skip去除已经处理过的元素。当然，到那时，你已经有了 LINQ，所以你也可以这样做：

return currentList.AddRange(ListElementsDivisibleBy3Recursive(input.SkipWhile(i => i % 3 != 0).ToList()));

当然，这需要枚举两次，因为您无法从 SkipWhile 中获取值。但是你根本不需要递归，你可以这样写：

return currentList.Where( i => (i % 3) == 0).ToList();

Answer 3

如果你真的想通过递归来解决这个问题，你可以这样做

static List<int> FilterMod3Internal(List<int> state, List<int> initialList, int index)
{
    if (index >= initialList.Count())
    {
        return state;
    }
    else
    {
        var number = initialList[index];
        if (number%3 == 0)
        {
            state.Add(number);

        }

        return FilterMod3Internal(state, initialList, index + 1);
    }
}
static List<int> FilterMod3(List<int> list)
{
    return FilterMod3Internal(new List<int>(), list, 0);
}

但是正如其他答案所指出的那样，当可以通过迭代（或至少尾递归）完成时，递归地做几乎任何事情都是一个坏主意。

如果你想在不使用更多内存的情况下过滤现有集合，你可以这样做

static void FilterListMod3Internal(List<int> list, int index)
{
    if (index >= list.Count())
    {
        return;
    }

    var number = list[index];

    if (number%3 != 0)
    {
        list.RemoveAt(index);
        FilterListMod3Internal(list, index);
    }
    else
    {
        FilterListMod3Internal(list, index + 1);
    }
}

两个版本都是递归的，但它们需要有某种内部函数，它有额外的参数来维持函数调用之间的状态。

你也可以像这样概括这种方法

static List<T> FilterInternal<T>(List<T> state, List<T> initialList, int index, Func<T, bool> filterFunction)
{
    if (index >= initialList.Count())
    {
        return state;
    }
    else
    {
        var item = initialList[index];
        if (filterFunction(item))
        {
            state.Add(item);

        }

        return FilterInternal(state, initialList, index + 1, filterFunction);
    }
}
static List<T> Filter<T>(List<T> list, Func<T, bool> filterFunction)
{
    return FilterInternal<T>(new List<T>(), list, 0, filterFunction);
}

以及不消耗额外内存的那个

static void FilterListInternal<T>(List<T> list, int index, Func<T, bool> filterFunction)
{
    if (index >= list.Count())
    {
        return;
    }

    var item = list[index];

    if (!filterFunction(item))
    {
        list.RemoveAt(index);
        FilterListInternal(list, index, filterFunction);
    }
    else
    {
        FilterListInternal(list, index + 1, filterFunction);
    }
}

static void FilterList<T>(List<T> list, Func<T, bool> filterFunction)
{
    FilterListInternal<T>(list, 0, filterFunction);
}

其中 filterFunction 应该 return 当您希望项目出现在结果集合中时为真，否则为真。很容易改变，所以，去试试吧，你想要的。

Answer 4

奇怪的问题:-)

这是更灵活的解决方案：IList RecursiveFilter 的扩展方法接受谓词和 return IEnumerable（可用于构造列表、数组或其他东西） .

using System;
using System.Collections.Generic;

namespace Sandbox
{
    class Program
    {
        static void Main()
        {
            var array = new[] { 1, 6, 8, 3, 6, 2, 9, 0, 7, 3, 5 };
            var filtred = array.RecursiveFilter(i => i % 3 == 0);

            foreach (var item in filtred)
                Console.WriteLine(item);
        }
    }

    public static class MyCollectionExtensions
    {
        public static IEnumerable<T> RecursiveFilter<T>(this IList<T> collection, Func<T, bool> predicate, int index = 0)
        {
            if (index < 0 || index >= collection.Count)
                yield break;
            if (predicate(collection[index]))
                yield return collection[index];
            foreach (var item in RecursiveFilter(collection, predicate, index + 1))
                yield return item;
        }         
    }
}

Answer 5

递归遍历一个列表来过滤它并不是一个特别适合可变数组支持列表的算法。这是一种更适合处理不可变结构的方法。在处理不可变列表时（通常建模为具有当前项和 link 到另一个节点的节点）递归解决方案非常适合这个问题：

public class Node<T>
{
    public Node(T value, Node<T> tail)
    {
        Value = value;
        Tail = tail;
    }

    public T Value { get; private set; }
    public Node<T> Tail { get; private set; }
}

public static Node<int> ListElementsDivisibleBy3Recursive(Node<int> node)
{
    if (node == null)
        return node;
    else if (node.Value % 3 == 0)
        return new Node<int>(node.Value, ListElementsDivisibleBy3Recursive(node.Tail));
    else
        return ListElementsDivisibleBy3Recursive(node.Tail);
}

我们有一个简单的递归情况，其中节点为空（每个列表的末尾都有一个 Tail 即 null）。然后我们有两种递归情况，或者当前节点的值与过滤器匹配，我们创建一个新列表，该节点在头部，尾部是列表其余部分的递归解决方案，或者当前节点的值不应该被包括在内，解决方案只是列表尾部的递归。

A List<T> 根本不适合这种类型的算法，因为它依赖于能够计算 "a list with everything after the first item" 以及也很容易计算 "a new list that is equal to the old list but with one item added to it"，两者都不是List<T> 可以轻松或高效执行的操作，但不可变列表通常将作为主要操作。

Answer 6

这是我能想到的唯一方法。每次递归都会删除最后一个元素，直到列表为空，然后当递归展开时，将满足条件的元素添加回列表的末尾。

List<int> ListElementsDivisibleBy3Recursive(List<int> input) {
    if (input.Count > 0) {
        int last = input.Last();
        input.RemoveAt(input.Count - 1);
        input = ListElementsDivisibleBy3Recursive(input);
        if (last % 3 == 0)
            input.Add(last);
    }
    return input;
}

虽然从方法中 return 任何东西都毫无意义，因为 input 是根据需要修改的，而不管 return 值如何。所以这实现了相同的结果：

void ListElementsDivisibleBy3Recursive(List<int> input) {
    if (input.Count > 0) {
        int last = input.Last();
        input.RemoveAt(input.Count - 1);
        ListElementsDivisibleBy3Recursive(input);
        if (last % 3 == 0)
            input.Add(last);
    }
}

递归过滤不可变列表

Filter an immutable list recursively

c#

arrays

recursion

list