Iterative process vs a recursive process

Question

Reading through SICP Distilled and trying to wrap my head around iterative vs recursive processes. The example given is:

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

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

Which of these is an iterative process (state is maintained entirely by the parameters to an iterative function) and which is a recursive process (state must be preserved "behind-the-scenes" while waiting for the previous function calls to finish.

My guess here is that the second is iterative because the arguments can be evaluated before the arguments are applied to the function, whereas the former will have to keep successive function calls on the stack waiting for the last + operation to finish before it can unwind the stack, running inc at each step.

Óscar López Óscar López · Accepted Answer · 2018-09-05T09:48:19

There's an easy way to tell apart an iterative process from a recursive one, ask yourself: is there anything left to do after the recursive call? If the answer is yes, then is a recursive process, that's what's happening here:

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

If the answer is no, then it's an iterative process, which is what happens here:

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

In the second case we say that + is in tail position, and an interpreter that supports it will optimise it, see: tail call. Clojure can't do tail call optimisation, unless you use recur.

Iterative process vs a recursive process

1 Answers