Tuesday, June 18, 2013

Print a string in reverse using recursion

In simple words, Recursion is nothing but a function calling itself. How can we solve this problem using recursion? 
Initially pass the entire string as input to the function. Basically a pointer to the first character is passed. This function examines the next character; if it is not null, it calls itself by advancing the pointer to the next character. This call sequence goes on until the next character is a null.
In the last call, it prints the last character and function call returns. When this call returns, it goes to the previous state. that means it prints the last but one character and so on...

Here the simple C++ code to do this.



#include <iostream>
#define MAXLEN 100
using namespace std;

void printRev(char *str)
{
 //return if empty string
 if( *str == NULL )
  return;
 
 //if the next char is not null, recurse
 if( *(str+1) != NULL )
  printRev(str+1);
  
 //print char while unwinding the stack
 cout<<*str;
}
int main()
{
 char str[MAXLEN];
 cin>>str;
 printRev(str);
 return 0;
}