CODEWITHSUNDEEP
algorithmrecursionschemerackettail-recursion
Matthew Butterick
Matthew Butterick

Reputation: 1074

How to achieve tail recursion on a tree-shaped data structure

I'm using Racket but the question would apply to any Scheme, where tail recursion is supported.

I'm familiar with the traditional pattern for achieving tail recursion on a flat list, which is roughly like so:

(define (func x [acc null])
  (if (null? x)
      acc
      (func (cdr x) (cons (do-something-to (car x)) acc))))

In this case, func is in tail position.

But when I'm working with a tree, i.e., a list with recursively nested lists, I end up doing recursive descent with map like so:

(define (func2 x)
  (cond
    [(atom? x) (do-something-to x)]
    [(list? x) (map func2 x)]))

This works, but func2 is no longer in tail position.

Could you — and if so, how would you — rewrite func2 in a tail-recursive way?

(Leaving aside the question of whether it improves performance, which is not the question I'm asking.)

Upvotes: 1

Views: 407

Answers (2)

Tudor Berariu
Tudor Berariu

Reputation: 4910

As it was already correctly stated and explained in the other answer, there's no advantage of using tail recursion on this. But, as you were interested in the way it would be done, here it is a deep-map function I have implemented once. The code is cleaner if you're satisfied with the mirrored list.

(define deep-map
  (λ (f lst)
    (let tail-rec ([stack `(,lst)] [acc '(())])
      ;(displayln (~a "Stack: " stack " / Acc: " acc))
      (cond [(null? (car stack))
             (if (null? (cdr stack))
                 (car acc)
                 (tail-rec (cdr stack)
                           `(,(append (cadr acc) `(,(car acc))) . ,(cddr acc))))]
            ;; The first element is a list and is being put on the stack
            [(list? (caar stack))
             (tail-rec `(,(caar stack) . (,(cdr (car stack)) . ,(cdr stack)))
                       `(() . ,acc))]
            ;; Process next element
            [else (tail-rec `(,(cdar stack) . ,(cdr stack)) 
                            `(,(append (car acc) `(,(f (caar stack)))) . ,(cdr acc)))]
            ))))

A simple example:

> (deep-map add1 '(1 ((2) 3)))
Stack: ((1 ((2) 3))) / Acc: (())
Stack: ((((2) 3))) / Acc: ((2))
Stack: (((2) 3) ()) / Acc: (() (2))
Stack: ((2) (3) ()) / Acc: (() () (2))
Stack: (() (3) ()) / Acc: ((3) () (2))
Stack: ((3) ()) / Acc: (((3)) (2))
Stack: (() ()) / Acc: (((3) 4) (2))
Stack: (()) / Acc: ((2 ((3) 4)))
'(2 ((3) 4))

Upvotes: 2

C. K. Young
C. K. Young

Reputation: 223133

You technically "can", by introducing an accumulator that acts as a stack. Your function would only be done when the stack is empty.

However, this has the same memory usage requirements as using the function call stack (i.e., non-tail recursion), so usually you don't gain anything by doing that.

Upvotes: 2

Related Questions