Итерационный процесс против рекурсивного процесса

Question

Прочитав SICP Distilled и пытаясь обернуться вокруг итеративных и рекурсивных процессов . Приведенный пример:

(defn + [a b]
  (if (= a 0) b (inc (+ (dec a) b))))

(defn + [a b]
  (if (= a 0) b (+ (dec a) (inc b))))

Какой из них является итеративным процессом (состояние полностью поддерживается параметрами итеративной функции), а какой является рекурсивным процессом (состояние должно сохраняться "за кадром", ожидая завершения предыдущих вызовов функции .

My угадайте здесь, это то, что второй является итеративным, потому что аргументы могут быть оценены до аргументов, примененных к функции, тогда как первый должен будет поддерживать последовательные вызовы функций на стек ожидает завершения последней операции +, прежде чем он сможет размотать стек, выполняя inc на каждом шаге.

Answer 1

Существует простой способ отличить итеративный процесс от рекурсивного, спросите себя: остается ли что-нибудь сделать после рекурсивного вызова? Если ответ да, то это рекурсивный процесс, вот что здесь происходит:

(inc (+ (dec a) b))
  ^
this is invoked after the recursive call

Если ответ отрицательный, то это итеративный процесс, который происходит здесь:

(+ (dec a) (inc b))
 ^
the recursive call is the last thing we do

Во втором случае мы говорим, что + находится в хвостовой позиции, и поддерживающий его интерпретатор оптимизирует его, см .: tail call . Clojure не может выполнить оптимизацию хвостового вызова, если вы не используете recur.