DaniWeb Forum Index > Software Development > C

C RSS

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

•

Join Date: Jun 2005

Posts: 16

Reputation: mina1984 is an unknown quantity at this point

Solved Threads: 0

mina1984

Offline

Newbie Poster

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

Jul 2nd, 2005

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

•

Join Date: Jun 2005

Posts: 60

Reputation: zyruz is an unknown quantity at this point

Solved Threads: 5

zyruz

Offline

Junior Poster in Training

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

Jul 2nd, 2005

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

•

Join Date: Sep 2004

Posts: 7,622

Reputation: Narue has a reputation beyond repute

Solved Threads: 714

Narue

Offline

Code Goddess

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

Jul 2nd, 2005

>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.

I'm here to prove you wrong.

•

Join Date: Jun 2005

Posts: 2,039

Reputation: Rashakil Fol is just really nice

Solved Threads: 139

Rashakil Fol Rashakil Fol is offline

Offline

Super Senior Demiposter

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

Jul 3rd, 2005

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:

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
int gcd(int x, int y)
{
    if (y == 0) {
        return x;
    }
    return gcd(y, x % y);
}
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:

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
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. */
}
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.

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
int gcd(int x, int y)
{
top:
    if (y == 0) {
        return x;
    }
    int tmp = x;
    x = y;
    y = tmp % y;
    goto top;
}
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:

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
int gcd(int x, int y)
{
    while (y) {
        int tmp = x;
        x = y;
        y = tmp % y;
    }
    return x;
}
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.