Scheme: the procedure is recursive, but is the process recursive or iterative?

Question

so I'm not sure if I finally understood it or maybe I'm still wrong. Is it correct that:

(define (add-one x)
  (+ x 1))

(define (sub-one x)
  (- x 1))

(define (add-numbers x y)
  (if (zero? y)
          x
          (add-numbers (add-one x) (sub-one y))))

... add-numbers is a recursive procedure and a recursive process and...

(define (add-numbers2 x y)
  (if (zero? y)
          x
          (add-numbers2 (+ x 1) (- y 1))))

... add-numbers2 is a recursive procedure and an iterative process?

Answer 1

Both are recursive syntactically, but both generate iterative computational processes. In the first function:

(define (add-numbers x y)
  (if (zero? y)
          x
          (add-numbers (add-one x) (sub-one y))))

Then, if y is not zero, what happens is that the thing needs to evaluate (add-numbers (add-one x) (sub-one y)), and to do this it needs to call (add-one x) and (add-one y), and then call add-numbers on the two results, with the result of the whole function being whatever this call to add-numbers returns. The important thing is that the call to add-numbers is the very last thing that happens. There's no need to return back to the point when that function call was made, as there's nothing more to do except return the calculated value. This means the process is iterative.

In the second version:

(define (add-numbers2 x y)
  (if (zero? y)
          x
          (add-numbers2 (+ x 1) (- y 1))))

Well, the easy way to see that this is the same is to realize that + and - are just functions, so this is exactly the same thing! The only difference is that + and - happen to be functions defined by the implementation, rather than by you.

Here is a version which really describes a recursive computational process:

(define (add-numbers3 x y)
  (if (zero? y)
      x
      (+ 1 (add-numbers3 x (- y 1)))))

In this version, if y is not zero then the function has to call itself on x and the result of subtracting 1 from y ... and then, once it's done that, it still needs to add 1 to the result of that call. So it needs to keep a memory that there is this pending operation of adding 1, and then actually do that addition when it returns from that function call. It's perhaps easier to see this using your original functions:

(define (add-numbers4 x y)
  (if (zero? y)
      x
      (add-one (add-numbers4 x (sub-one y)))))

Now you can clearly see that when the recursive call to add-numbers4 returns there is still more work to do.

Answer 2

@tb explains both processes are iterative, and that is correct. We can visualise the process as -

(add-numbers 3 5)
(add-numbers 4 4)
(add-numbers 5 3)
(add-numbers 6 2)
(add-numbers 7 1)
(add-numbers 8 0)
8

See how it stays nice and flat? That is a linear process. And with a tiny modification, we can spawn an entirely different process -

(define (add-numbers x y)
  (if (zero? y)
      x
      (+ 1 (add-numbers x (- y 1))))

Notice how the process deepens as dependent values are computed, until it finally collapses to a return value. This is a recursive process -

(add-numbers 3 5)
(+ 1 (add-numbers 3 4))
(+ 1 (+ 1 (add-numbers 3 3)))
(+ 1 (+ 1 (+ 1 (add-numbers 3 2))))
(+ 1 (+ 1 (+ 1 (+ 1 (add-numbers 3 1)))))
(+ 1 (+ 1 (+ 1 (+ 1 (+ 1 (add-numbers 3 0))))))
(+ 1 (+ 1 (+ 1 (+ 1 (+ 1 3)))))
(+ 1 (+ 1 (+ 1 (+ 1 4))))
(+ 1 (+ 1 (+ 1 5)))
(+ 1 (+ 1 6))
(+ 1 7)
8