Python, изменяющий строку, используя рекурсию

Question

Я хочу использовать рекурсию, чтобы перевернуть строку в python, чтобы она отображала символы в обратном направлении (т. Е. «Hello» станет «olleh» / «o l l e h».

Я написал один, который делает это итеративно:

def Reverse( s ):
    result = ""
    n = 0
    start = 0
    while ( s[n:] != "" ):
        while ( s[n:] != "" and s[n] != ' ' ):
            n = n + 1
            result = s[ start: n ] + " " + result
            start = n
    return result

Но как именно я делаю это рекурсивно? Я запутался в этой части, особенно из-за того, что я мало работаю с Python и рекурсией.

Любая помощь будет оценена.

Answer 1

def rreverse(s):
    if s == "":
        return s
    else:
        return rreverse(s[1:]) + s[0]

(Очень немногие люди выполняют тяжелую рекурсивную обработку в Python, язык не предназначен для него .)

Answer 2

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

Каково первое, что вы делаете при обращении строки? Буквально первое? Вы получаете последний символ строки, верно?

Таким образом, обратный символ строки является последним символом, за которым следует обратный знак , но последний символ, в который входит рекурсия. Последний символ строки можно записать как x[-1] пока все но последний символ x[:-1].

Теперь, как вы "снизу"? То есть, какой тривиальный случай вы можете решить без рекурсии? Одним из ответов является односимвольная строка, которая одинакова вперед и назад. Итак, если вы получите односимвольную строку, все готово.

Но пустая строка еще более тривиальна, и кто-то может фактически передать это вашей функции, поэтому мы, вероятно, должны использовать это вместо этого. В конце концов, односимвольная строка может быть также разбита на последний символ и все, кроме последнего символа; просто все, кроме последнего символа, является пустой строкой. Поэтому, если мы обработаем пустую строку, просто вернув ее, мы настроены.

Соберите все вместе, и вы получите:

def backward(text):
    if text == "":
        return text
    else:
        return text[-1] + backward(text[:-1])

или в одну строку:

backward = lambda t: t[-1] + backward(t[:-1]) if t else t

Как уже отмечали другие, это не тот способ, которым вы обычно делаете это в Python. Итеративное решение будет быстрее, а использование нарезки будет еще быстрее.

Кроме того, Python накладывает ограничение на размер стека, и нет оптимизации хвостового вызова, поэтому рекурсивное решение будет ограничено обращением строк длиной всего около тысячи символов. Вы можете увеличить размер стека Python, но все равно будет установлен фиксированный предел, в то время как другие решения всегда могут обработать строку любой длины.

Answer 3

Если это не просто вопрос домашнего задания, и вы на самом деле пытаетесь перевернуть строку для какой-то большей цели, просто наберите s[::-1].

Answer 4

def reverse_string(s):
    if s: return s[-1] + reverse_string(s[0:-1])
    else: return s

или

def reverse_string(s):
    return s[-1] + reverse_string(s[0:-1]) if s else s