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

Функция fib-rec помимо значения fib(n) возвращает второе значение: fib(n-1). Пользователь, вызывающий функцию fib-rec, может ничего не знать об этом втором значении.

(defun fib-rec (n)
  ;; Values: 1) fib(n)
  ;;         2) fib(n-1)
  (cond ((= n 0) 0)
	((= n 1) (values 1 0))
	(t (multiple-value-bind (v1 v2) (fib-rec (1- n))
             (values (+ v1 v2) v1)))))

Оценка времени и памяти - линейная:

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