Объяснение рекурсивной функции reverse_string

Концепция рекурсии заключается в том, что вы вызываете одну и ту же функцию до тех пор, пока не встретите базовый случай. В вашем случае базовый случай — это когда len(string) == 0, где вы возвращаете пустую строку to the caller, which was a previous version of the same function reverse_strings, но с другими параметрами (обычно это более «сложная» функция).

Предположим, у вас есть эта простая строка hi, ваша функция будет вести себя так:

1. Проверьте, достигнут ли базовый случай, если да, верните пустую строку, в противном случае перейдите к следующему оператору. Поскольку у нас нет пустой строки, мы переходим к следующему оператору.

2. Следующий оператор вызывает ту же функцию reverse_strings, но с другими параметрами, чем когда вы вызываете ее в первый раз для ее запуска; на самом деле, когда вы вызываете его в первый раз, вы делаете что-то вроде этого reverse_strings('hi'). В else вы вызываете функцию с уменьшенной версией вашей строки hi, обратите внимание на следующий оператор: return reverse_strings(string[1:]) + string[0] что string[1:] это просто i. Теперь у вас есть return reverse_strings('i') + string[0]. Обратите внимание, что string[0] равно H. Здесь, reverse_strings('i'), как я сказал выше, вы снова вызываете свою функцию, но с меньшей версией вашей строки i.

3. Теперь мы находимся внутри другого вызова функции. Оценивается первый оператор if len(string) == 0: return ''. Это правда? Нет, потому что len(string) все равно отличается от 0. Итак, мы переходим к следующему оператору else: return reverse_strings(string[1:]) + string[0]. Теперь обратите внимание, что мы собираемся снова вызвать ту же функцию. но с меньшей строкой, в данном случае пустой строкой, поскольку string[1:] из i является пустой строкой. Таким образом, наш звонок можно резюмировать следующим образом: return reverse_strings('') + i.

4. Теперь мы находимся в другой «упрощенной версии» reverse_strings. Первый оператор оценивается if len(string) == 0: return ''. Это правда? Да, потому что, помните, наша строка теперь пустая. Теперь происходит то, что вы возвращаете вызывающей стороне пустую строку, которая является функцией в пункте 3.

5. Теперь мы только что вернули вызывающей стороне пустую строку в точке 3, поэтому у нас есть return '' + i. '' + i — это не что иное, как просто i, которое вы собираетесь вернуть вызывающей стороне этой функции по указателю 3, которая является функцией в точке 2.

6. Теперь вы только что вернули вызывающему абоненту i, в частности, вы только что вернули i этому оператору return reverse_strings('i') + string[0], где string[0] — это H, а reverse_strings('i') — это просто i, которое вы только что вернули. Итак, теперь у вас есть iH, и вы только что перевернули строку.

Он использует нарезку, чтобы объединить первую букву в конец, а затем снова передать вторую букву оставшимся буквам в рекурсивную функцию.

string[1:] при первом звонке — это ello string[0] это h:

2-й рекурсивный вызов string[1:] -> llo string[0] -> e

3rd string[1:] ->lo string[0] -> l

4th string[1:] ->o string[0] -> l

5th string[1:] ->"" string[0] -> o

Таким образом, reverse_strings(string[1:]) вызывает функцию, рекурсивно перемещающуюся по строке, а string[0] объединяет каждую букву, начиная с конца, что и возвращается в конце.

График ниже может помочь:

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

1: if len(string) == 0: return ''
2: else: return reverse_strings(string[1:]) + string[0]

Я назову первый элемент строки (string[0]) ее головой, а оставшуюся часть (string[1:]) ее концом. Если строка состоит всего из 1 символа, мы считаем ее конец пустой строкой. С точки зрения этого словаря, вот правила того, что значит перевернуть строку:

1. Перевернутая пустая строка — это пустая строка.
2. Любая другая перевернутая строка — это перевернутая версия ее хвоста, за которой следует ее голова.

В случае, например, abcd мы применяем правило 2, поскольку правило 1 не применяется:

• abcd в обратном порядке равно bcd в обратном порядке, за которым следует a.

Хорошо, что bcd перевернуто? Ну, мы можем применить то же правило:

• bcd в обратном порядке равно cd в обратном порядке, за которым следует b.

и вниз по цепочке:

• cd в обратном порядке - это d в обратном порядке, за которым следует c,
• d в обратном порядке равно '' в обратном порядке, за которым следует d,
• '' перевернуто на '' по правилу 1, потому что это пустая строка.

Возвращаясь к этому списку, вы получаете:

• '', затем d, затем c, затем b, затем a

это dcba, это то, что мы хотели!

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