На этом шаге мы кратко перечислим содержание последующих шагов.

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

Здесь процесс выполнения рекурсивных программ рассматривается с разных точек зрения, некоторые из которых являются чисто "умозрительными". Тут же вводится понятие дерева рекурсии - распространённое графическое представление последовательности вызовов рекурсивных программ. Среди его достоинств - удобство отладки, помощь в вычислении функций, наглядность оценки вычислительной (временн0й и пространственной) сложности рекурсивных программ, а также покрытие всех рассмотренных ранее разновидностей рекурсии. Кроме этого, тут описывается тесное взаимодействие рекурсивных программ со стеком - структурой данных, используемой ими при вызовах подпрограмм (методов).

Заканчивается изложение кратким введением в мемоизацию - стратегию, которая сокращает временную сложность рекурсивных методов путём сохранения результатов потенциально затратных вызовов. Мемоизация тесно связана с таким важным методом проектирования алгоритмов, как динамическое программирование.

Независимо от того, рекурсивны или нет выполняемые программой методы, важно понимать правила их вызова. Рассмотрим код из примера 10.1 для вычисления косинуса угла между двумя n-мерными векторами согласно определениям (3.14), (3.15) и (3.16).

Пример 10.1. Методы для вычисления косинуса угла между двумя n-мерными векторами

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import math


def dot_product(u, v):
    s = 0
    for i in range(0, len(u)):
        s = s + u[i] * v[i]
    return s


def norm_Euclidean(v):
    return math.sqrt(dot_product(v, v))


def cosine(u, v):
    return dot_product(u, v) / norm_Euclidean(u) / norm_Euclidean(v)  


# Example
a = [2, 1, 1]
b = [1, 0, 1]
print(cosine(a, b))

Архив с файлом можно взять здесь.

На рисунке 1 приводится цепочка (нерекурсивных) вызовов подпрограмм (тёмные стрелки) и возвратов из них (светлые стрелки) при выполнении этого кода.

Рис.1. Цепочка вызовов-возвратов методов из примера 10.1

Блоки в правых верхних углах функций содержат конкретные параметры, приводящие к конечному результату √3 / 2. Числа в кружочках обозначают последовательность выполнения действий. Очевидно, но крайне важно то, что полное завершение подпрограммы невозможно до полного завершения всех вызвавших её методов.

То же самое – для рекурсивного кода. На рисунке 2 приведена цепочка рекурсивных вызовов функции sum_first_naturals() из примера 1.1 для начального значения n = 4.

Рис.2. Цепочка вызовов-возвратов для sum_first_naturals(4)

При выполнении рекурсивного условия метод вызывает сам себя (уменьшая исходное значение на 1) и снова переходит к первой своей инструкции. Крайне важно понимать, что процесс не завершается с выполнением начального условия (n = 1). Ведь до этого метод уже вызывал себя несколько раз, поэтому программа должна выполняться до полного завершения каждого из этих рекурсивных вызовов. Непонимание этой последней цепочки действий, известной под названием "пассивный поток" (passive flow), - одна из главных причин искажённого представления о рекурсии. Наконец, вся цепочка действий алгоритма может быть проверена построчно шаг за шагом методами отладчика. Такие инструментальные средства доступны в большинстве интегрированных сред разработки.

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

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