Coding Exercise: Reverse String Using Recursion

Write recursive function to reverse string e.g., "hello" → "olleh".

Two approaches: index swapping or substring building.

Problem Statement

Input: string str

Output: reversed string

Examples: "abc" → "cba", "hello" → "olleh", "" → ""

Approach 1: Index Swapping (In-place)

Swap first/last chars, recurse on middle.

              
            
C++

          In-place string reverse
        
#include <iostream>
#include <string>
using namespace std;

void reverseString(string &str, int start, int end) {
    // Base case
    if (start >= end) return;
    
    // Swap
    swap(str[start], str[end]);
    
    // Recurse middle
    reverseString(str, start+1, end-1);
}

int main() {
    string s = "hello";
    reverseString(s, 0, s.length()-1);
    cout << s << endl;  // olleh
    return 0;
}

Approach 2: Substring Building

Return last char + reverse(first chars).

              
            
C++

          Build new reversed string
        
string reverseString(string str) {
    // Base cases
    if (str.empty() || str.length() == 1) {
        return str;
    }
    
    // Last char + reverse rest
    return reverseString(str.substr(1)) + str[0];
}

// Usage: cout << reverseString("hello");  // olleh

Dry Run: reverseString("abc", 0, 2)

              
TEXT

          Swapping trace
        
Initial: a b c  [0,2]

Step 1: swap(0,2) → c b a  [1,1]
Step 2: start>=end → STOP

Result: cba ✓

Test Cases

              
            
TEXT

          Expected outputs
        
""     → ""
"a"    → "a"
"ab"   → "ba"
"abc"  → "cba"
"racecar" → "racecar"

Complexity

Approach 1: Time O(n), Space O(n) - recursion stack

Approach 2: Time O(n^2), Space O(n) - string copies

Practice Variations

1. Reverse words in sentence

2. Check palindrome recursively

3. Reverse array of integers

Conclusion

Mastered string recursion! Index swapping is efficient.

Next: Array sum or binary search recursively.