- It is mutually recursive with
iter. Its call to
iter is not in
itself (properly) recursive.
- 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
(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:
iter calls itself twice.
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
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]
(empty? things) answer
(pair? (first things))
(recur (rest things) (cons (deep-reverse (first things)) answer))
:else (recur (rest things) (cons (first things) answer))))