Recursive String Reverse

Recursive String Reverse

Hard C Functions 35 views
Explanation Complexity

Problem Statement

Use WITHOUT loop recursively to reverse the string. Clearly define base case and recursive case. Compare with Iterative approach.

Input Format

A string.


Output Format

The reversed string.

Example

"hello"


"olleh"

Constraints

• String length ≥ 0

• No loop is allowed in the recursive solution

Concept Explanation

String reversal using recursion works by breaking the problem into smaller parts.
Each recursive call handles a smaller substring, and characters are reversed while returning back from recursion.

Step-by-Step Explanation

1.Function ko string pass karo.

2.Base case:

• Agar string empty ho ya length 1 ho → string return karo.

3.Recursive case:

• Pehla character alag karo.

• Baaki string ke liye function ko dubara call karo.

4.Recursive call se jo string mile:

• Uske end me pehla character jod do.

5.Final reversed string return ho jaayegi.

Concept Explanation

String reversal using recursion works by breaking the problem into smaller parts.
Each recursive call handles a smaller substring, and characters are reversed while returning back from recursion.

Step-by-Step Explanation

1.Function ko string pass karo.

2.Base case:

• Agar string empty ho ya length 1 ho → string return karo.

3.Recursive case:

• Pehla character alag karo.

• Baaki string ke liye function ko dubara call karo.

4.Recursive call se jo string mile:

• Uske end me pehla character jod do.

5.Final reversed string return ho jaayegi.

Input / Output Format

Input Format
A string.


Output Format
The reversed string.
Constraints
• String length ≥ 0

• No loop is allowed in the recursive solution

Examples

Input:
"hello"
Output:
"olleh"

Example Solution (Public)

C 
#include <stdio.h>
#include <string.h>

/* Recursive function to reverse a string in place */
void reverseRecursive(char str[], int start, int end) {
    /* Base case: start >= end -> stop recursion */
    if (start >= end)
        return;

    /* Swap characters at start and end */
    char temp = str[start];
    str[start] = str[end];
    str[end] = temp;

    /* Recursive call for inner substring */
    reverseRecursive(str, start + 1, end - 1);
}

/* Iterative reversal using loop */
void reverseIterative(char str[]) {
    int i, j;
    char temp;
    int n = strlen(str);

    for (i = 0, j = n - 1; i < j; i++, j--) {
        temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
}

int main() {
    char str1[100], str2[100];

    printf("Enter a string: ");
    scanf("%s", str1);

    /* Copy string for iterative method */
    strcpy(str2, str1);

    /* Recursive reversal */
    reverseRecursive(str1, 0, strlen(str1) - 1);
    printf("Reversed string (recursive): %sn", str1);

    /* Iterative reversal */
    reverseIterative(str2);
    printf("Reversed string (iterative): %sn", str2);

    return 0;
}

Official Solution Code

#include <stdio.h>
#include <string.h>

/* Recursive function to reverse a string in place */
void reverseRecursive(char str[], int start, int end) {
    /* Base case: start >= end -> stop recursion */
    if (start >= end)
        return;

    /* Swap characters at start and end */
    char temp = str[start];
    str[start] = str[end];
    str[end] = temp;

    /* Recursive call for inner substring */
    reverseRecursive(str, start + 1, end - 1);
}

/* Iterative reversal using loop */
void reverseIterative(char str[]) {
    int i, j;
    char temp;
    int n = strlen(str);

    for (i = 0, j = n - 1; i < j; i++, j--) {
        temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
}

int main() {
    char str1[100], str2[100];

    printf("Enter a string: ");
    scanf("%s", str1);

    /* Copy string for iterative method */
    strcpy(str2, str1);

    /* Recursive reversal */
    reverseRecursive(str1, 0, strlen(str1) - 1);
    printf("Reversed string (recursive): %sn", str1);

    /* Iterative reversal */
    reverseIterative(str2);
    printf("Reversed string (iterative): %sn", str2);

    return 0;
}
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.