C Program to Reverse a String using Recursion

To reverse a string, we have to reverse the sequence the characters of string. First character of original string should become last character in reversed string, second character of original string should become second last character of reversed string and so on.

For Example
Input: CProgramming
Output (Reversed String): gnimmargorPC

To reverse a string of length N using recursion, we have to swap the leftmost and rightmost characters of a string and then recursively reverse the inner sub-string from index 1 to N-2. Keep on repeating this unless size of sub-string is greater than one.

Algorithm to reverse a string using recursion Let inputString is a string (character array) of length N and leftIndex and rightIndex are two integer variable.

Initialize leftIndex and rightIndex to index of first character and last character of string respectively(leftIndex = 0; and rightIndex = N-1;)
We will first swap leftmost(inputString[leftIndex]) character and rightmost(inputString[rightIndex]) character then recursively reverse sub array from index leftIndex+1 to rightIndex-1.
Recursion will terminate when leftIndex > rightIndex.

Below is the recursive equation to reverse a string. Swap function interchanges the positions of leftmost and rightmost characters of substring.

reverse(string, leftIndex, rightIndex) = swap(string, leftIndex, rightIndex) + 
                                         reverse(string, leftIndex+1, rightIndex-1)

Suppose, we want to reverse string “ORANGE” using recursion. We will first call reverse function by passing following parameters
reverse(“ORANGE”, 0, 5). Then reverse function will swap the positions of character ‘O'(leftmost character) and ‘E'(rightmost character) and recursively calls itself to reverse inner substring as reverse(“ERANGO”, 1, 4) and so on. Recursion will terminate when size of sub-string becomes zero.

C program to reverse a string using recursion

Below program uses a user defined recursive function named ‘reverseString’ which takes a pointer to a string and leftmost and rightmost index of a sub-string to be reversed. It reverse the sequence of characters of the string between leftIndex and rightIndex(both inclusive). First of all, reverseString does input validation then it swaps the leftmost and rightmost characters of the substring pointed by leftIndex and rightIndex using a local character variable. Then it recursively calls itself to reverse inner sub-string from leftIndex+1 to rightIndex-1.

C Program to Reverse a String using Recursion 1

/*
* C Program to reverse a string using recursion
*/
#include <stdio.h>
#include <string.h>
#include <conio.h>
 
char* reverseString(char *string, int leftIndex, int rightIndex);
 
int main()
{
   char inputArray[100];
  
   printf("Enter a string to reverse\n");
   gets(inputArray);
    
   reverseString(inputArray, 0, strlen(inputArray) - 1);
   printf("Reversed string\n%s", inputArray);
   getch();
   return 0;
}
 
/*
 * Function to reverse an array 
 * @input inputArray leftIndex and rightIndex
 */
char* reverseString(char *string, int leftIndex, int rightIndex){
      char ch;
      if(NULL == string || leftIndex > rightIndex)
          return NULL;
      /*
       * Swap leftMost and rightMost character, 
       * and recursively call reverseString for inner sub-array
       */
      ch = string[leftIndex];
      string[leftIndex] = string[rightIndex];
      string[rightIndex] = ch;
       
      reverseString(string, leftIndex + 1, rightIndex - 1);
      return string;
}

C program to reverse a string using recursion

Related