0

How does this code work?? I am at a loss how the tail recursion works here?

#include<iostream.h>
#include<conio.h>
void back(void);
void main(void)
{
cout<<"Enter a sentence: ";
back();
getch();
}
void back(void)
{
char ch;
ch=getche();
if (ch!='\r')
{back();
cout<<ch;//Read a character, print the rest of the input in reverse, then print that character"
}
else
cout<<"Output in reverse order is: \n";
}
3
Contributors
2
Replies
13
Views
2 Years
Discussion Span
Last Post by mike_2000_17
Featured Replies
  • There's no tail recursion in that function. For tail recursion to apply, you generally need to have nothing appearing after the recursive call (the call to "back()"). In this case, a character is printed out after the recursive call, which means that the character value must be retained through the … Read More

0

Get a long list of letters in the input buffer. Let's say the input is "abcde" and then "/r" because you press enter.

First function gets the first letter, "a", then calls the function again.
   Second function gets "b", calls function again.
       Third function gets "c", calls function again.
           Fourth function gets "d", calls function again.
               Fifth function gets "e", calls function again.
                   Six function gets "/r" so does NOT call function
                   again. Instead, it outputs "Output in reverse 
                   order is: \n" and finishes.
               Fifth function outputs its letter and finishes.
           Fourth function outputs its letter and finishes.
       Third function outputs its letter and finishes.
    Second function outputs its letter and finishes.
First function outputs its letter and finishes.

Edited by Moschops

2

There's no tail recursion in that function. For tail recursion to apply, you generally need to have nothing appearing after the recursive call (the call to "back()"). In this case, a character is printed out after the recursive call, which means that the character value must be retained through the recursive call, which breaks tail recursion (or makes tail-call optimization impossible). If someone claimed that this code uses tail recursion, then that person is wrong.

The easiest way to tell if something can be tail-call optimized is to see if you can manually translate the function into an iterative one (instead of recursive) and see if you can do it without auxiliary memory. In this case, there is no way to do that iteratively without having O(N) memory. For example, one way to do this iteratively is to store all the characters into an array and then traverse that array in reverse to print out the characters, which implies that you need an array of N characters to make this work. The recursive form you have there does the same thing, except that the characters are stored in function-call stack-frames instead of in a simple array, which is just inefficient and bad style (and unsafe, by the way).

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.