CODEWITHSUNDEEP
functionrecursionschemereversetail-recursion
jcubic
jcubic

Reputation: 66650

How to create tail recursive reverse list procedure?

This is similar question to this one How to Reverse a List? but for iterative (tail recursive) function. How can I create such function? Is it possible?

Upvotes: 0

Views: 2387

Answers (2)

dercz
dercz

Reputation: 962

or even more explicit:

    (define (reverse xs)
     (let loop ((pend xs)
                (res '()))
       (if (null? pend)
           res
           (loop (cdr pend) (cons (car pend) res)))))

The fold answer by Chris is more neat and can be better wrt performance (for various reasons). As of second part of your question it is always possible, i.e. every function can be made tail-recursive (e.g. by transforming to cps, which can be done mechanically).

Upvotes: 2

C. K. Young
C. K. Young

Reputation: 223183

Yes; in fact the standard implementation of reverse is totally tail-recursive.

(define (reverse xs)
  (fold cons '() xs))

Don't like using fold? No problem:

(define (reverse xs)
  (do ((result '() (cons (car xs) result))
       (xs xs (cdr xs)))
      ((null? xs) result)))

Upvotes: 2

Related Questions