Converting recursion to iteration

Question

I've done some reading, and learned the best way to convert recursion to iteration is to use stacks. It's been hard to implement though, because of how return values are used. Any assistance would be fantastic. Here is the recursive function:

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;
}

The code below doesn't work but it shows my attempt so far

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;
}

Can you show any of the work you have done to convert this? — Scott Hunter
– Scott Hunter, Commented Oct 27, 2015 at 0:40
Yes, I wasn't going to add it in to make the question simpler because my solution of course isn't functional. Anyway, I just appended it to my question details. — John
– John, Commented Oct 27, 2015 at 0:45
@ThomasLevesque: Any recursive method can be converted to an iterative method. Hint: can you convert the method into continuation passing style? If the answer is yes, can you then see how to convert the CPS version into an iterative algorithm? — Eric Lippert
– Eric Lippert, Commented Oct 27, 2015 at 1:06
@John: You don't want to convert this to CPS; my point is that Thomas's idea that a method that does two recursive calls cannot be made iterative is false; all recursive methods can be turned into CPS, and all CPS programs can be made iterative, but this fact is of use to compiler designers, not to line of business programmers. What you should do rather is simplify your algorithm down to its essence. — Eric Lippert
– Eric Lippert, Commented Oct 27, 2015 at 1:15
If you are interested in learning about CPS, which is fascinating, I have a gentle introduction for JavaScript programmers here: blogs.msdn.com/b/ericlippert/archive/tags/… start at the bottom. — Eric Lippert
– Eric Lippert, Commented Oct 27, 2015 at 1:18

Community · Accepted Answer · 2017-05-23 10:27:56Z

When you look at the code, essentially, recursivity is obtained and stops like that:

array of N => by recursion, calculate 2 arrays of N/2, and then combine them

when N==1, it is finished.

Then, you calculate every 2. N/2, 4. N/4, ... 2^n . N/2^n , where n=log2(N)

Datas seems not to be re-usable, so you have to calculate 2^n arrays.

If your size is a power of 2, 64 for example, you will have to calculate 64 arrays, then 32, 16, 8, 4, 2, 1, then 127 operations (=2^(n+1)-1).

So question becomes: how to convert from recursive operations in a binary tree to iterations.

I selected other posts from SO with the same general problematic: you can find algorithm and code there:

Post order traversal of binary tree without recursion

Convert recursive binary tree traversal to iterative

The more general problem of converting from recursion to iteration depends on the algorithm of recursion, and if datas are re-usable.

hope it helps !

Collectives™ on Stack Overflow

Converting recursion to iteration

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related