c# - 将递归转换为迭代

Question

我读了一些书，了解到将递归转换为迭代的最佳方法是使用堆栈。但是，由于返回值的使用方式，它很难实现。任何帮助都会很棒。这是递归函数:

public Complex[] fft(Complex[] x, int L) {
    int ii;
    int kk = 0;
    int N = x.Length;

    Complex[] Y = new Complex[N];

    if (N == 1) {
        Y[0] = x[0];
    } else {

        Complex[] E = new Complex[N / 2];
        Complex[] O = new Complex[N / 2];
        Complex[] even = new Complex[N / 2];
        Complex[] odd = new Complex[N / 2];


        for (ii = 0; ii < N; ii++) {
            if (ii % 2 == 0) {
                even[ii / 2] = x[ii];
            }
            if (ii % 2 == 1) {
                odd[(ii - 1) / 2] = x[ii];
            }
        }

        E = fft(even, L);   // RECURSION HERE
        O = fft(odd, L);    // RECURSION HERE

        // RECURSION RESULTS USED HERE
        for (kk = 0; kk < N; kk++) {
            Y[kk] = E[(kk % (N / 2))] + O[(kk % (N / 2))] * twiddles[kk * (L / N)];
        }
    }

    return Y;
}

下面的代码不起作用，但它显示了我到目前为止的尝试

public Complex[] fft2(Complex[] x, int L) {
    Stack<Complex[]> stack = new Stack<Complex[]>();
    stack.Push(x);

    int ii;
    int kk;
    int N;

    while (stack.Count > 0) {
        x = stack.Pop();
        kk = 0;
        N = x.Length;

        Complex[] Y = new Complex[N];

        if (N == 1) {
            Y[0] = x[0];
        } else {

            Complex[] E = new Complex[N / 2];
            Complex[] O = new Complex[N / 2];
            Complex[] even = new Complex[N / 2];
            Complex[] odd = new Complex[N / 2];

            for (ii = 0; ii < N; ii++) {
                if (ii % 2 == 0) {
                    even[ii / 2] = x[ii];
                }
                if (ii % 2 == 1) {
                    odd[(ii - 1) / 2] = x[ii];
                }
            }

            stack.Push(even);
            stack.Push(odd);

            // E = fft2(even, L);
            // O = fft2(odd, L);

            for (kk = 0; kk < N; kk++) {
                Y[kk] = E[(kk % (N / 2))] + O[(kk % (N / 2))] * twiddles[kk * (L / N)];
            }
        }
    }

    return Y;
}

Answer 1

当你看代码时，本质上，递归是这样获得的，停止:

N 数组 => 通过递归，计算出2个N/2的数组，然后组合

当N==1时，结束

然后，您计算每 2. N/2, 4. N/4, ... 2^n 。 N/2^n ，其中 n=log2(N)

数据好像不能复用，所以要计算2^n个数组。

如果你的大小是2的幂，例如64，你将要计算64个数组，然后是32、16、8、4、2、1，然后是127次操作(=2^(n+1)- 1).

那么问题就变成了:如何将二叉树中的递归操作转换为迭代。

我从 SO 中选择了其他具有相同一般问题的帖子:您可以在那里找到算法和代码:

Post order traversal of binary tree without recursion

Convert recursive binary tree traversal to iterative

从递归转换为迭代的更普遍的问题取决于递归算法，以及数据是否可重用。

希望对您有所帮助!