Исследование хвостовой рекурсии в вычислителе

С помощью отслеживания стека исследуйте хвостовую рекурсию в нашем вычислителе (раздел 5.4.2). Запустите вычислитель и определите итеративную процедуру factorial из раздела 1.2.1:

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

Запустите эту процедуру с несколькими небольшими значениями n. Для каждого из этих значений запишите максимальную глубину стека и количество операций сохранения, потребных для вычисления n!.

а. Вы увидите, что максимальная глубина стека, нужная для вычисления n!, от n не зависит. Какова эта глубина?

б. Составьте на основе своих данных формулу в зависимости от n числа операций сохранения, необходимых для вычисления n! для любого n ≥ 1. Обратите внимание, что число операций — линейная функция от n и, следовательно, определяется двумя константами.


Комментарии отсутствуют.

Необходима авторизация

Вы должны авторизоваться для создания комментария.

Вход