Cтек в вычислении чисел Фибоначчи с помощью древовидной рекурсии

Проследите за использованием стека в вычислении чисел Фибоначчи с помощью древовидной рекурсии:

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

а. Дайте формулу, зависящую от n , для максимальной глубины стека, требуемой при вычислении Fib(n) при n ≥ 2 . Подсказка: в разделе 1.2.2 мы утверждали, что требуемый объем памяти линейно зависит от n .

б. Постройте формулу для количества сохранений, требуемых при вычислении Fib(n) , если n ≥ 2 . Вы увидите, что количество сохранений (которое хорошо коррелирует со временем исполнения) экспоненциально растет с ростом n . Подсказка: пусть требуется S(n) сохранений при вычислении Fib(n) . Нужно показать, что имеется формула, которая выражает S(n) в зависимости от S(n − 1) , S(n − 2) и некоторой фиксированной «дополнительной» константы k , независимой от n . Приведите эту формулу и найдите, чему равно k . Покажите теперь, что S(n) выражается как aFib(n + 1) + b и укажите значения a и b .

---