Here is a 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.
- 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.
#include <stdio.h>
#include <string.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);
return 0;
}
char* reverseString(char *string, int leftIndex, int rightIndex){
char ch;
if(NULL == string || leftIndex > rightIndex)
return NULL;
ch = string[leftIndex];
string[leftIndex] = string[rightIndex];
string[rightIndex] = ch;
reverseString(string, leftIndex + 1, rightIndex - 1);
return string;
}
Output
Enter a string to reverse TECHCRASHCOURSE Reversed string ESRUOCHSARCHCET
Related Topics