0
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

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))))
Improve this answer
$\endgroup$
0
$\begingroup$

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).

Improve this answer
$\endgroup$
6
  • $\begingroup$ The recursive call to iter looks tail recursive to me. Translating into Clojure and using the explicitly tail-recursive recur confirms this. The call to deep-reverse is not a tail call. Are you referring to tail-call-optimisation or the use of continuation-passing style to reduce general recursion to tail-recursion? $\endgroup$ Commented Jul 7, 2019 at 12:08
  • $\begingroup$ I mean tail call optimization. $\endgroup$ Commented Jul 7, 2019 at 12:10
  • $\begingroup$ TCO can't turn the deep-reverse call into an iteration. $\endgroup$ Commented Jul 7, 2019 at 12:15
  • $\begingroup$ Yes, this is precisely what I say in my answer. $\endgroup$ Commented Jul 7, 2019 at 12:16
  • $\begingroup$ The phrase these functions appears to refer to deep-reverseand iter, implying the opposite of what you intend. $\endgroup$ Commented Jul 7, 2019 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.