На этом шаге мы рассмотрим пример реализации такого потока.

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

def mystery_method_1(s):
    if s:
        print(s[0], end='')
        mystery_method_1(s[1:])  


def mystery_method_2(s):
    if s:
        mystery_method_2(s[1:])  
        print(s[0], end='')


s = 'Word'
mystery_method_1(s)
print()
mystery_method_2(s)

    Подобно примерам на рисунках 1 и 2 предыдущего шага, разберём эти процедуры, проследив цепочку выполняемых ими действий. На рисунке 1 приведена цепочка действий mystery_method_1() для входной строки s = 'Word', где в полях рядом со стрелками показывается состояние экрана при вызове и по завершении рекурсивной процедуры.

Рис.1. Цепочка вызовов-возвратов для рекурсивной функции mystery_method_1("Word")

    При первом вызове метода экран пуст. Затем, поскольку s не пустая строка, выводится её первый символ ('W') и вызывается тот же метод с остатком строки ('ord'). Эти два шага повторяются, пока аргумент метода не станет пустой строкой. Достигнув этого начального условия, программа выведет на экран символ за символом всю исходную строку 'Word'. После чего метод завершается и возвращает управление предыдущему вызову, который также завершается. Это повторяется, пока не завершится каждый из вызовов. В итоге данная процедура просто выводит на экран исходную строку. В заключение заметьте, что в методе реализована хвостовая рекурсия, так как рекурсивный вызов - это последняя операция в рекурсивном условии. Таким образом, алгоритм решает задачу при выполнении начального условия. Отметьте, что экран не меняется по завершении рекурсивных вызовов.

    Напротив, метод mystery_method_2() тоже выводит на экран исходную строку, но в обратном порядке. На рисунке 2 приведена цепочка вызовов метода.

Рис.2. Цепочка вызовов-возвратов для функции mystery_method_2("Word")

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

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

    На следующем шаге мы рассмотрим деревья рекурсии.

Предыдущий шаг Содержание Следующий шаг