Древовидная рекурсия и рост повторной работы
Наивное вычисление чисел Фибоначчи ветвится на перекрывающиеся вызовы и повторяет работу, тогда как итеративный процесс делает один шаг на индекс.
Как две процедуры могут возвращать одно и то же значение Фибоначчи, когда их потребности во времени и памяти растут по-разному?
- Распознавание дерева вызовов с перекрывающимися подзадачами
- Подсчет рекурсивных применений отдельно от возвращаемого значения
- Отслеживание максимальной глубины рекурсии как сохраняемого состояния процесса
- Сравнение экспоненциального роста дерева с линейными итеративными шагами
- Чтение конечных измерений в их точно наблюдаемой области
Прямая процедура fib создает два меньших вызова всякий раз, когда n не меньше 2. Эти ветви перекрываются, так как fib 3 появляется внутри обеих ветвей fib 5, и тот же шаблон повторяется ниже. Возвращенное число не содержит этой повторяющейся истории, поэтому calls и maximum-depth делают форму процесса видимой.
Для n, равного 8, инструментальное дерево возвращает 21 после 67 применений процедуры и достигает глубины 8. Итеративный процесс переносит два последовательных значения Фибоначчи вместе со счетчиком remaining и достигает того же значения за восемь переходов. Для этой хрестоматийной пары время наивной рекурсии растет экспоненциально, тогда как глубина растет линейно, а время итерации растет линейно, тогда как число переменных состояния остается постоянным. Отображаемые счетчики точно фиксируют выбранные программы и входные данные.
- Вывод
- —
- Значение
- —
- Диагностика
- —
Первая программа возвращает (21 67 8). Вторая возвращает ((4 3 9 4) (5 5 15 5) (6 8 25 6) (7 13 41 7)).
Найдите каждое применение, которое разделяется на n минус 1 и n минус 2, затем обратите внимание на повторяющиеся вызовы с тем же меньшим значением n. Сравните быстро растущее поле calls с итеративным полем steps, которое увеличивается ровно на единицу для каждого запрошенного индекса. Трасса выполнения с фиксированным ограничением может прекратить запись до завершения вычисления, если достигнут предел событий.
Измените программу и сравните результат.
Предположите значение, число рекурсивных вызовов и максимальную глубину для n, равного 9, затем сравните их с числом итеративных шагов до запуска измененной программы.
Показать подсказку
Числа рекурсивных вызовов продолжаются как 9, 15, 25, 41, 67, 109, тогда как итеративный процесс использует n переходов.