c# - 如何将此递归函数转换为迭代函数？

Question

我无法将此方法从递归转换为迭代。我特别遇到的问题是我不知道如何转换作为 if 条件的递归调用。陈述。

这需要完成，因为我使用的数据集会导致堆栈溢出异常。

必须有一堆索引，这些索引是当前用于递归调用的参数，但除此之外，我不知道该怎么做。

    public static IEnumerable<BipartiteMatch> MaximumBipartiteMatch(int m, int n, Func<int, int, bool> isMapped)
    {
        var matches = new int[n];

        for (var i = 0; i < n; ++i)
        {
            matches[i] = -1;
        }

        for (var x = 0; x < m; x++)
        {
            BipartiteMatch(x, n, new bool[n], matches, isMapped);
        }

        for (var index = 0; index < n; index++)
        {
            yield return new BipartiteMatch(matches[index], index);
        }
    }

    private static bool BipartiteMatch(int x, int n, bool[] seen, int[] matches, Func<int, int, bool> isMapped)
    {
        for (var y = 0; y < n; y++)
        {
            if (seen[y] || !isMapped(x, y)) continue;

            seen[y] = true;

            //HERE:
            if (matches[y] >= 0 && !BipartiteMatch(matches[y], n, seen, matches, isMapped)) continue;

            matches[y] = x;
            return true;
        }

        return false;
    }

如 matches[y] >= 0 ，那么我们需要推送 matches[y] 的值到堆栈，但我不确定如何循环它以便模拟递归。

我的尝试(有问题):

internal static class MaximumMatchingAlgorithm
{
    internal static IEnumerable<BipartiteMatch> Solve(int m, int n, Func<int, int, bool> isMapped)
    {
        const int invalid = -1;

        var mappings = new Stack<int>[m];
        var matches = new int[n];

        for (var index = 0; index < n; index++)
        {
            matches[index] = invalid;
        }

        for (var x = 0; x < m; x++)
        {
            var mapping = mappings[x] = new Stack<int>(n);

            for (var y = 0; y < n; y++)
            {
                if (isMapped(x, y))
                {
                    mapping.Push(y);
                }
            }

            var currentX = x;

            while (mapping.TryPop(out var y))
            {
                var tempX = matches[y];
                var otherMapping = tempX != invalid ? mappings[tempX] : null;

                if (otherMapping == null)
                {
                    matches[y] = currentX;
                    break;
                }

                if (otherMapping.Count == 0) continue;

                matches[y] = currentX;
                currentX = tempX;
                mapping = otherMapping;
            }
        }

        for (var index = 0; index < n; index++)
        {
            yield return new BipartiteMatch(matches[index], index);
        }
    }
}

更新:

这是我在@EricLippert 发表评论后的第二次尝试。我创建了一个 State值来存储循环停止的位置，以便它可以模拟递归期间可能发生的暂停。某处仍然存在错误，但我认为这可能会越来越近。

    public struct State
    {
        public int X { get; set; }

        public int Y { get; set; }

        public bool Result { get; set; }
    }

    public static void BipartiteMatch(int x, int n, bool[] seen, int[] matches, Func<int, int, bool> isMapped)
    {
        var stack = new Stack<State>();
        stack.Push(new State {X = x, Y = -1});

        while (stack.TryPop(out var state))
        {
            if (state.Y != -1 && state.Result)
            {
                matches[state.Y] = state.X;
            }
            else
            {
                for (var y = state.Y != -1 ? state.Y : 0; y < n; y++)
                {
                    if (seen[y] || !isMapped(state.X, y)) continue;

                    seen[y] = true;

                    if (matches[y] >= 0)
                    {
                        stack.Push(new State {X = state.X, Y = y});
                        stack.Push(new State {X = matches[y], Y = -1});
                        break;
                    }

                    if (stack.TryPop(out state))
                    {
                        stack.Push(new State {X = state.X, Y = state.Y, Result = true});
                        break;
                    }

                    matches[y] = state.X;
                    return;
                }
            }
        }
    }

Answer 1

我想我可能已经想通了，但在我说这一切都很好之前，我想再征求一下意见。

这里的逻辑是每次使用递归时，将循环的当前状态连同可以回答先前堆叠状态是否有效的状态一起插入堆栈。如果问题的答案为真，则整个堆栈展开并终止该方法，否则继续搜索。

    public readonly struct State
    {
        public State(int x, int y = 0)
        {
            X = x;
            Y = y;
        }

        public int X { get; }

        public int Y { get; }
    }

    public static void BipartiteMatch(int x, int n, bool[] seen, int[] matches, Func<int, int, bool> isMapped)
    {
        var stack = new Stack<State>(new[] {new State(x)});

        while (stack.TryPop(out var state))
        {
            for (var y = state.Y; y < n; y++)
            {
                if (seen[y] || !isMapped(state.X, y)) continue;

                seen[y] = true;

                if (matches[y] >= 0)
                {
                    stack.Push(new State(state.X, y));
                    stack.Push(new State(matches[y]));
                    break;
                }

                matches[y] = state.X;

                while (stack.TryPop(out state))
                {
                    matches[state.Y] = state.X;
                }

                break;
            }
        }
    }