python обращение строки с помощью рекурсии

<p>я хочу использовать рекурсию для обращения строки в python, чтобы она отображала символы задом наперед (т. е. "hello" станет "olleh"/"o l l e h").</p><p>я написал один, который делает это итеративно:</p><pre><code>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 </code></pre><p>но как именно я делаю это рекурсивно? я запутался в этой части, особенно потому, что я не очень много работаю с python и рекурсией.</p><p>любая помощь будет оценена.</p>

<pre><code>def rreverse(s): if s == "": return s else: return rreverse(s[1:]) + s[0] </code></pre><p>(очень немногие люди выполняют тяжелую рекурсивную обработку в python, язык <a href="http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html">не был разработан для этого</a> .)</p>

<p>чтобы рекурсивно решить проблему, найдите тривиальный случай, который легко решить, и выясните, как добраться до этого тривиального случая, разбив задачу на более простые и простые версии.</p><p>каково первое, что вы делаете при обращении строки? буквально первое? вы получаете последний символ строки, верно?</p><p>таким образом, обратная строка является последним символом, за которым следует обратная сторона всего <em>но</em> последний символ, в который входит рекурсия. последний символ строки можно записать как <code>x[-1]</code>, тогда как все <em>но</em> последний символ <code>x[:-1]</code>.</p><p>теперь, как вы "дна"? то есть, какой тривиальный случай вы можете решить без рекурсии? одним из ответов является односимвольная строка, которая одинакова вперед и назад. итак, если вы получите односимвольную строку, все готово.</p><p>но пустая строка еще более тривиальна, и кто-то может фактически передать это в вашу функцию, поэтому мы, вероятно, должны использовать это вместо этого. в конце концов, односимвольная строка <em>также</em> может быть разбита на последний символ и все, кроме последнего символа; просто все, кроме последнего символа, является пустой строкой. поэтому, если мы обработаем пустую строку, просто вернув ее, мы настроены.</p><p>соберите все это вместе, и вы получите:</p><pre><code>def backward(text): if text == "": return text else: return text[-1] + backward(text[:-1]) </code></pre><p>или в одну строку:</p><pre><code>backward = lambda t: t[-1] + backward(t[:-1]) if t else t </code></pre><p>как уже отмечали другие, это не тот способ, которым вы обычно делаете это в python. итеративное решение будет быстрее, а использование нарезки будет еще быстрее.</p><p>кроме того, python накладывает ограничение на размер стека, и нет оптимизации хвостового вызова, поэтому рекурсивное решение будет ограничено обращением строк длиной всего около тысячи символов. вы можете увеличить размер стека python, но все равно будет установлен фиксированный предел, в то время как другие решения всегда могут обработать строку любой длины.</p>

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

<pre><code>def reverse\_string(s): if s: return s[-1] + reverse\_string(s[0:-1]) else: return s </code></pre><p>или же</p><pre><code>def reverse\_string(s): return s[-1] + reverse\_string(s[0:-1]) if s else s </code></pre>