Thread: iterative, recursion, always possible?

Originally posted by Vber
Most programmers says that always is possible to change an recursion into a iterative one, but I'm stuck here:

Code:

void rec(depth){
      if (depth==0) 
          return; 
     for(int i=0;i<30;i++) 
           return rec(depth-1);
}

How to change this into an iterative one?
Can't understand how..

[list=1][*]What is meant by

Code:

void rec(depth)

What is the type of depth?
I assume it is int

Code:

void rec(int depth)

[*] The loop in

Code:

for(i=0;i<30;i++) return rec(depth-1);

does the same job as

Code:

return rec(depth-1);

A return in a loop breaks the loop[/list=1]

So your program keeps on decreasing depth till 0 and then does nothing if depth>0
else it is an infinite sequence of nothingness

so

Code:

void  rec(int depth)
{
    if (depth >= 0) return;
    while(1);
}

should do the job.

Originally posted by pinko_liberal
so

Code:

void  rec(int depth)
{
    if (depth >= 0) return;
    while(1);
}

should do the job.

Actually, depth will wrap at -2147483648, meaning that 0 will always be reached even if the number is negative.

Code:

void rec(int depth)
{
   return;
}

does the same...

Originally posted by pinko_liberal

Code:

for(i=0;i<30;i++) return rec(depth-1);

does the same job as

Code:

return rec(depth-1);

Not quite. The issue I believe is to explain what it is doing, and how to produce an interative example that does the same thing. The two examples are not identical. The first does the work 30x for each time the function is called. The second does not. This is actually a huge difference.

Think if we pass it the number 10.

1 call with the value of 10.
30 calls with the value of 9.
30 x 30 calls of the value 8.
30 x 30 x 30 calls of the value 7.

See where I'm going with this? This is a huge difference as far as your CPU is concerned. Imagine if we had passed it a big number.

Quzah.

Originally posted by quzah
Not quite. The issue I believe is to explain what it is doing, and how to produce an interative example that does the same thing. The two examples are not identical. The first does the work 30x for each time the function is called. The second does not. This is actually a huge difference.

Think if we pass it the number 10.

1 call with the value of 10.
30 calls with the value of 9.
30 x 30 calls of the value 8.
30 x 30 x 30 calls of the value 7.

See where I'm going with this? This is a huge difference as far as your CPU is concerned. Imagine if we had passed it a big number.

Quzah.

No it doesnt
The second loop operatates just once, return breaks the loop, so it is always a loop of length 1.
It can be verfied by adding a printf call at the point of entry - so that printf is called every time rec is called. Even the original function involves n+1 function calls for a positive input n.

Code:

#include <stdio.h>
void rec(int depth)
{
      int i;       	
      printf("depth=%d\n",depth); 
      if (depth==0) 
          return; 
     for(i=0;i<30;i++) 
           return rec(depth-1);
}

int main(void)
{
	rec(10);
	return 0;
}

Output

Code:

depth=10
depth=9
depth=8
depth=7
depth=6
depth=5
depth=4
depth=3
depth=2
depth=1
depth=0

Ah. I see. I didn't see the return. Probably because it's absurd to have it there, so the logical portion of my brain rejected it...

Quzah.

Originally posted by Magos
Actually, depth will wrap at -2147483648, meaning that 0 will always be reached even if the number is negative.

Code:

void rec(int depth)
{
   return;
}

does the same...

You are right.
After depth reaches INT_MIN, the next number will be the postive (INT_MIN-1)%(INT_MAX+1).
By 6.2.5.9

A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.

Originally posted by pinko_liberal
You are right.
After depth reaches INT_MIN, the next number will be the postive (INT_MIN-1)%(INT_MAX+1).
By 6.2.5.9

Sorry I was wrong, (signed) integer overflow invokes undefined behavior, the above is not correct.