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 define
s:
(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))))