Saturday, September 28, 2013

Print a string in reverse using recursion

The following function is simply based on recursion mechanism. We write a function printReverse(). Initially we call this function by passing a pointer to the first character of the string. We keep calling this function recursively by incrementing the pointer until we reach the null character (End of the string). If we reach null, the function returns and we print the character at the current pointer.

Since the function calling mechanism uses a stack to keep track the calling sequence. While unwinding the stack, we are able to print the characters in reverse.

For example printReverse("hello") function calling sequence looks like the following.

printReverse("hello")
  printReverse("ello")
    printReverse("llo")
      printReverse("lo")
        printReverse("o")
          printReverse("")
            return
        print "O"
      print "l"
    print "l"
  print "e"
print "h"


Here is the C++ code for the same

#include <iostream>

using namespace std;

void printReverse(char *str)
{
 if( *str )
 {
  printReverse(str+1);
  cout<<(*str);
 }  
}
int main()
{
 char str[] = "reverse this";
 printReverse(str);
 return 0;
}