Обратное использование строки без переменных при использовании рекурсии в c ++

Question

Как вы можете перевернуть строку, используя рекурсию, следуя ограничениям, указанным в функции

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

Answer 1

Вот краткая реализация второго подхода, описанного в ответе Робо. По сути, вернуть последний элемент строки, соединенный с обратным расположением других элементов.

#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;
}

Answer 2

Для любой рекурсивной задачи нам нужен 1) один шаг, который приближает нас к решению, 2) рекурсивный вызов для меньшей задачи и 3) базовый случай, из которого мы можем немедленно вернуться.

Я предлагаю, чтобы единственным шагом было поменять местами первый и последний символы, одновременно передавая все внутренние символы в рекурсивный вызов.

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

Итак, reverse_recurse("abcd") возвращает d + reverse_recurse(bc) + a.

В нашем базовом случае вообще не должно быть работы. Если исходная строка имеет четное количество символов, тогда базовый случай - это когда переданная строка forward является пустой строкой. Если исходная строка имеет нечетное количество символов, базовый случай - это, когда вход forward имеет один символ (средний символ из исходной строки).

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]

Если вы понимаете, что я предложил, вы можете реализовать это на C ++. (Подсказка: std::string::substr() существует.)

РЕДАКТИРОВАТЬ 1

В комментариях SergeyA предлагает более простую альтернативу. Единственный шаг - выделить последний символ, и рекурсивный вызов выполняется для строки «все, кроме самого последнего»:

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

РЕДАКТИРОВАТЬ 2

Теперь, так как крайний срок выполнения домашних заданий пройден, вот моя реализация.

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