Сложение - итерация

(defun iter+ (n m)
  (if (= n 0)     	; базис рекурсии
      m
      (iter+ (1- n) (1+ m))))

(iter+ 3 4)
→ (iter+ 2 5)
→ (iter+ 1 6)
→ (iter+ 0 7)
→ 7

Итеративный процесс можно описать:

• конечным набором переменных состояния
• заранее заданным правило, определяющее, как переменные состояния изменяются от шага к шагу,
• тестом на завершение, когда процесс должен закончить работу.

• время = O(n) - линейно-итеративный процесс
• память = O(1)

Фиксированный объём памяти нужно понимать с оговоркой. Наивная реализация рекурсии с помощью стека вызовов означает линейный рост и памяти. Но многие Лисп-компиляторы осуществляют оптимизацию концевой рекурсии (tail recursion). Преобразованные вычисления, действительно, будут выполнятся как итеративный процесс и требовать фиксированный объем памяти.