На этом шаге мы рассмотрим особенности рекурсивной реализации такого алгоритма.

Итерационный подход может быть применён для создания рекурсивных хвостовых алгоритмов для многих задач. Рассмотрим более сложную задачу преобразования системы счисления. Представим себе итерационный алгоритм, выполняющий шаги по приведению десятичного числа 142 к основанию 5 (1032₅) согласно таблице 1.

Таблица 1. Состояния итерационной программы приведения числа 142 к основанию 5 (1032₅) из примера 11.5
n b p s

142 5 1 0

28 5 10 2

5 5 100 32

1 5 1000 32

0 5 10000 1032

Таблица 1. **Состояния итерационной программы приведения числа 142 к основанию 5 (1032₅) из примера 11.5**
n	b	p	s
142	5	1	0
28	5	10	2
5	5	100	32
1	5	1000	32
0	5	10000	1032

Помимо параметров, методу необходима переменная s, в которой будет храниться промежуточный результат, а в итоге – результат. Кроме того, дополнительная переменная p содержит степень 10, необходимую для обновления значения s. На каждом шаге n изменяется путём целочисленного деления на основание b (n // b), p умножается на 10, а переменная-накопитель s увеличивается на (n % b) * p. Этот итерационный алгоритм приведён в примере 11.5, где изначально p = 1 и s = 0. Наконец, когда n достигает значения 0, метод может возвратить результат, находящийся в s.

Пример 11.5. Итерационный алгоритм приведения неотрицательного целого десятичного числа n к основанию b

1
2
3
4
5
6
7
8

def decimal_to_base_iterative(n, b):  
    s = 0
    p = 1
    while n > 0:
        s = s + (n % b) * p
        p = p * 10
        n = n // b
    return s

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

Аналогичная хвостовая рекурсивная функция должна моделировать итерации цикла вызовами самой себя. Переменные (и параметры) итерационной версии должны стать параметрами рекурсивных вызовов, а сама рекурсивная функция должна воспроизвести их обновления в теле итерационного цикла (строки 5-7). Наконец, начальное условие выполняется при n = 0, когда метод может вернуть значение переменной s, так как она будет содержать окончательный результат. В примере 11.6 приведена хвостовая рекурсивная функция вместе с методом-оболочкой, который инициализирует р единицей, а s - нулём. Обратите внимание на то, как аргументы рекурсивного вызова отражают изменение переменных итерационного алгоритма в теле цикла.

Пример 11.6. Хвостовая рекурсивная функция приведения числа к основанию b и метод-оболочка

1
2
3
4
5
6
7
8
9
10

def decimal_to_base_tail(n, b, p, s):  
    if n == 0:
        return s
    else:
        return decimal_to_base_tail(n // b, b, p * 10,  
                                    s + (n % b) * p)


def decimal_to_base_tail_wrapper(n, b):
    return decimal_to_base_tail(n, b, 1, 0)

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

Хотя хвостовые рекурсивные функции в примерах 11.4 и 11.6, вне всяких сомнений, рекурсивны, такой способ их разработки соответствует парадигме императивного программирования, когда всё внимание сосредоточено на переменных и параметрах, определяющих состояние программы. Обратите внимание, что при разработке рекурсивного метода данный подход не опирается на декомпозицию задачи или индукцию. Вместо этого рекурсивные алгоритмы просто воспроизводят итерационные версии. По этой причине получаемые алгоритмы могут сбить с толку тех программистов, которые попытаются понять код с точки зрения декомпозиции задачи. Кроме того, из-за упомянутых на 162 шаге недостатков такой способ разработки, безусловно, следует избегать. (Для примеров 11.4 и 11.6 ошибки переполнения стека довольно редки, так как исходное значение факториала обычно небольшое, а высота дерева рекурсии для алгоритма преобразования к другому основанию является логарифмической функцией от n.) Таким образом, если к решению задачи применяется итерационный подход, то целесообразнее разрабатывать итерационный алгоритм.

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

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