changing loops (for to while) and (recursive to for)

[mina1984]

hi
im kind of confused about how to change a for loop into a while loop and how to change a recursive into a for loop and for loop into a recursive, i read books and searched online but it all seems confusing
could somebody please simplify it for me?

thanx in advance.

;)
mina

[zyruz]

Is this in general, or do you have a loop that you want to change?

[Narue]

>could somebody please simplify it for me?
No, but we can help you to understand it better if you'll do more than offer vague references to general techniques.

[Rashakil Fol]

Okay. Generally speaking, tail recursion (where the last thing to be executed is the recursive call) can be optimized to some kind of loop. Not necessarily a "for" loop. Here's a step by step process for doing it. We'll use the GCD example that lies in another thread. The greatest common divisor function, when defined recursively, looks like this:

int gcd(int x, int y)
{
    if (y == 0) {
        return x;
    }
    return gcd(y, x % y);
}

Now, the recursive call, gcd(y, x % y), can be interpreted as "Go back to the beginning of the function, with the new values for x and y being y and x%y, respectively."

So now we code that manually:

int gcd(int x, int y)
{
top: /* A label, used by the goto. */
    if (y == 0) {
        return x;
    }
    int param_1 = y; /* First assign to temporary variables */
    int param_2 = x % y;
    int x = param_1; /* Then set your 'new' values for x and y. */
    int y = param_2;
    goto top; /* Goto the top of the function. */
}

And the recursion has now been replaced by a loop. Further optimization can be done. For instance, if you carefully assign in the right order, only one temporary parameter holder is necessary.

int gcd(int x, int y)
{
top:
    if (y == 0) {
        return x;
    }
    int tmp = x;
    x = y;
    y = tmp % y;
    goto top;
}

It's not hard to see that this could be written as a while loop, which runs until y == 0:

int gcd(int x, int y)
{
    while (y) {
        int tmp = x;
        x = y;
        y = tmp % y;
    }
    return x;
}

Sometimes, you can't easily get rid of the goto (and then it's not worth eliminating the goto. But if we're going to talk about what is readable programming or not, we might as well leave in the tail-recursion and trust the compiler to optimize it away).

Now you can try to figure out on your own how to convert a loop to recursive form. It is similar to the reverse of this process.