Iteration vs Recursion question in Lisp method

Question

I am curious if the following method would be called iterative or recursive:

(define (deep-reverse items) (define (iter things answer) (cond ((null? things) answer) ((pair? (car things)) (iter (cdr things) (cons (deep-reverse (car things)) answer))) (else (iter (cdr things) (cons (car things) answer))))) (iter items ()))

I am confused because iter only calls itself with the state variables things and answer as arguments, and modifies those each run, so that I think it is iterative. It is defined in a method deep-reverse that does recursively call itself... This is confusing to me because there are elements both of iteration and recursion in this method, so that I don't know in the end how I would classify it... Is deep-reverse recursive? Is iter iterative?

Thank you.

Answer 1

Is deep-reverse recursive?

• It is mutually recursive with iter. Its call to iter is not in itself (properly) recursive.

Is iter iterative?

• Its calls to itself are iterative.
• Its call to deep-reverse is (properly) recursive.

It is not the functions as a whole,but each call within them that you can classify as iterative or recursive.

As you noticed, the iter function makes no use of its deep-reverse context. Better separate the functions into distinct defines:

(define (deep-reverse items)
  (iter items ()))

(define (iter things answer)
  (cond ((null? things) answer)
        ((pair? (car things)) 
          (iter (cdr things) (cons (deep-reverse (car things)) answer)))
        (else (iter (cdr things) (cons (car things) answer))))

These are mutually recursive:

• deep-reverse calls iter and
• iter calls deep-reverse.

And iter calls itself twice.

The deep-reverse call to iter and both the iter calls of itself are tail calls: they are the last thing done in the enclosing computation. They are in your terms iterative, though the first does not involve repetition. They could each be implemented as an appropriately set up control-jump/goto. Any Scheme compiler will short-circuit the calls in this way.

The call of deep-reverse from iter is different. The call is inside a cons. It can't be dug out. It is properly recursive, so needs some kind of stack to carry its nest of invocations.

---

I tested the above by translating the functions into Clojure, a Lisp dialect with explicit tail recursion using the reserved word recur instead of the function name. Here is the code:

(defn pair? [x]
  (and (coll? x) (next x)))

(defn deep-reverse [items]
  (iter items ()))

(defn iter [things answer]
  (cond
    (empty? things) answer
    (pair? (first things))
      (recur (rest things) (cons (deep-reverse (first things)) answer))
    :else (recur (rest things) (cons (first things) answer)))) 

Answer 2

Since deep-reverse and iter call each other, they are (mutually) recursive. Their combination is not tail recursive however, so deep-reverse is not iterative in the scheme parlance (IOW, does not admit tail call optimization).

PS. A proverbial sufficiently smart compiler (and, in fact, many real ones) can compile this function into an iteration (i.e., not using the function call stack).