Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How is this recursive function automatically converted into iterative function?

Tags:

c++

recursion

I am reading on tail recursion as below

Tail recursion refers to a recursive call at the last line. Tail recursion can be mechanically eliminated by enclosing the body in a while loop and replacing the recursive call with one assignment per function argument.

For example

void print(Iterator start, Iterator end, ostream& out=cout) {
  if(start == end)
      return;
  out << *start++ << endl;
  print(start, end, out);
}

is converted to iterative by above specification as

void print(Iterator start, Iterator end, ostream& out=cout) {
   while(true) {
      if(start == end)
          return;
      out << *start++ << endl;
    }
}

In above passage it is mentioned that "replacing recursive call with one assignment per function argument, but in given example we didn't have any assignment?

Can any one explain and provide example for above explanation about how to translate recursive to iterative function?

like image 568
venkysmarty Avatar asked Dec 07 '22 19:12

venkysmarty


2 Answers

The assignment is hidden in the increment operator:

start++;

is in fact an assignment:

start = start+1;

Actually, the example (part one) is not very good.

out << *start++ << endl;
print(start, end, out);

should be

out << *start << endl;
print( start+1, end, out);
like image 161
ur. Avatar answered Feb 15 '23 22:02

ur.


I don't think, whatever passage you are referring is important; just focus on the main problem, where you want to convert a recursive function to a normal iterative function, which can be done (effortlessly) as,

void print(Iterator start, Iterator end, ostream& out=cout) {
   while(start != end) {
      out << *start++ << endl;
    }
}
like image 43
iammilind Avatar answered Feb 15 '23 23:02

iammilind