Числа Фибоначи - древовидная рекурсия

(defun fib (n)
 (cond ((= n 0) 0)
       ((= n 1) 1)
       (t (+ (fib (- n 1))
             (fib (- n 2))))))

(fib 5)

Неэффективна: при каждом вызове обращается к самой себе дважды.

• время = O(cⁿ)
  Пропорционально числу вершин.
• память = O(n)
  Пропорциональна максимальной глубине дерева.
  В каждой точке требуется запоминать только те вершины, которые находятся выше по дереву.