Сложение - линейная рекурсия

(defun rec+ (n m)
  (if (= n 0)
      m
      (1+ (rec+ (1- n) m))))

• время = O(n)
• память = O(n)

Вычисление - цепочка отложенных операций. Интерпретатор запоминает их, чтобы выполнить впоследствии.