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?
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);
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;
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With