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, Oct 27 '15 at 00: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, Oct 27 '15 at 00:45
There's an excellent explanation of how to convert any recursive method (or set of mutually recursive methods) to iteration in http://www.amazon.com/Fundamentals-Computer-Algorithms-software-engineering/dp/0914894226 . In a nutshell, your stack needs to contain `` pairs, where the label (in C# an enum value) indicates where to jump (one of the two return sites) when it's popped. — Gene, Oct 27 '15 at 00:46
@John What is `twiddles`? Doesn't seem to be a local variable. — Asad Saeeduddin, Oct 27 '15 at 00:49
Converting recursion to iteration is possible when you make only one recursive call. But here there are two recursive calls, so AFAIK you can't convert it to an iterative form (at least not fully). — Thomas Levesque, Oct 27 '15 at 01:02
@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, Oct 27 '15 at 01: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, Oct 27 '15 at 01:15
Suppose your method is `int M(int x) { if (x < 0) return 0; return M(x - 1) + M(x - 2); }`. Can you make this much simpler method iterative? If so, then you can make your much more complicated method iterative. — Eric Lippert, Oct 27 '15 at 01:16
If you are interested in learning about CPS, which is fascinating, I have a gentle introduction for JavaScript programmers here: http://blogs.msdn.com/b/ericlippert/archive/tags/continuation+passing+style/ start at the bottom. — Eric Lippert, Oct 27 '15 at 01:18
Personally, I'd argue that moving the stack from the platform-implemented one to a privately maintained one doesn't change the recursive nature of the algorithm. I.e. you're not really converting to "iterative" if you're still using a stack. As far as the specific question goes, without [a good, _minimal_, _complete_ code example](https://stackoverflow.com/help/mcve) that reliably reproduces your problem, the question is off-topic for Stack Overflow. — Peter Duniho, Oct 27 '15 at 04:25
@EricLippert, interesting. I'm not very familiar with CPS, and didn't realize it could solve this problem. I'll go read your articles now ;) — Thomas Levesque, Oct 27 '15 at 08:58
@PeterDuniho you're talking about iterative *process*, but OP means *syntactic* property of a *procedure* (the distinction as per *SICP* ). — Will Ness, Oct 27 '15 at 09:19
@ThomasLevesque: Here's a way to think about it: suppose you made the method return a `Task` and then added an `await Task.Delay(1);` to run before every base and recursive case, and an `await` before each recursive call. And further suppose we are in a GUI app. Obviously that would make everything a lot slower, but that's not the point. The point is that now we are sitting in a loop -- the windows event processing loop -- and executing the *same program* in the *same order*, but the recursive calls use a *constant*, amount of stack, not O(n) stack. — Eric Lippert, Oct 27 '15 at 13:57
@ThomasLevesque: Since the program is now in a form that is using constant stack and sitting in a loop, plainly it is in a form that is essentially iterative, not recursive. If you took all the code that the compiler would generate on your behalf and refactored it into something readable, you'd have an iterative algorithm. My point is that this laborious process can be applied to *any* recursive algorithm, no matter how complicated. In practice this technique is really only of use to compiler writers; it's too painful to do it by hand. — Eric Lippert, Oct 27 '15 at 14:00

score 0 · Answer 1 · edited May 23 '17 at 10:27

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 !

Converting recursion to iteration

1 Answers1