CODEWITHSUNDEEP
c++recursion
Josh Rice
Josh Rice

Reputation: 81

Reverse a string using no variables while using recursion in c++

How can you reverse a string using recursion following the constraints mentioned in the function

string reverse_recurse(string forward) { // recursive
// Constraints: No loops allowed; no static local or global variables.
// Your new code goes here...
return ""; 
}

Upvotes: -5

Views: 214

Answers (3)

Sarath Govind
Sarath Govind

Reputation: 129

Here is an implementation using char[] array.

#include using namespace std;

void reverse(char* str, int index = 0) {

int StrLength = 0;

while (str[StrLength] != '\0') {

    StrLength++;

}

if (index >= StrLength / 2) return;

// Swap first and last character

swap(str[index], str[StrLength - index - 1]);


// Recursive call with the next index

reverse(str, index + 1);

}

int main() {

char str[] = "Welcome to world of CPP!";

reverse(str);

cout << "Reversed string: " << str << endl;

return 0;

}

Upvotes: 0

Robᵩ
Robᵩ

Reputation: 168796

For any recursion problem, we need 1) a single step that gets us closer to a solution, 2) a recursive call on a smaller problem, and 3) a base case from which we can return immediately.

I propose that the single step is to swap the first and final characters, while passing all of the interior characters to the recursive call. 

def reverse_recurse(forward):
    return forward[last] + 
           reverse_recurse(forward[second .. one_before_last]) +
           forward[0]

So, reverse_recurse("abcd") returns d + reverse_recurse(bc) + a.

Our base case should involve no work at all. If the original string has an even number of characters, then the base case is when the passed-in forward is the empty string. If the original string has an odd number of characters, the base case is when the passing-in forward has a single character (the middle character from the original string).

def reverse_recurse(forward):
    if forward.len() is 0 or 1:
        return forward
    return forward[last] + 
           reverse_recurse(forward[second .. one_before_last]) +
           forward[0]

If you understand what I've proposed, you can implement it in C++. (Hint: std::string::substr() exists.)

EDIT 1

In comments, SergeyA suggests an easier alternative. The single step is to isolate the final character and the recursive call is on the all-but-the-last string:

def reverse_recurse(forward):
    if forward.len() is 0 or 1:
        return forward
    return forward[last] + 
           reverse_recurse(forward[first .. one_before_last])

EDIT 2

Now, since the homework deadline is passed, here is my implementation.

string reverse_recurse(string forward) {
    if (forward.size() == 0)
        return forward;
    return reverse_recurse(forward.substr(1)) + forward.substr(0, 1);
}

Upvotes: 3

andypea
andypea

Reputation: 1401

Here is a quick implementation of the second approach described in Robᵩ's answer. Basically, return the last element of the string concatenated with the reverse of the other elements.

#include <iostream>
#include <string>

std::string reverse_string(std::string a_string) {
    return
      a_string.length() > 0 ?
        a_string.back()
          + reverse_string(a_string.substr(0, a_string.length() - 1)) :
        std::string();
}

int main() {
    std::string a_string = "live on time , emit no evil";

    std::cout << a_string << std::endl;
    std::cout << reverse_string(a_string) << std::endl;

    return 0;
}

Upvotes: 0

Related Questions