Wednesday, March 14, 2012

Recursion with no base case?

Here's my solution:
(define (all-descendants node-children root)
  (cons root
        (append-map (lambda (child)
                      (all-descendants node-children child))
                    (node-children root))))
I wasn't measuring, but it took me more than a minute. I spent most of that time thinking about transitive closures, queues, iterating over elements, etc., before I realized that since I'm working with a tree rather than a directed graph, I need not worry about shared structure or duplicate elements.

This is an example of a well-founded recursive program that does not have an explicit base case. append-map (mapappend in Common Lisp) implicitly does not call the mapped function if the list argument is empty, so the recursion ends at the nodes of the tree that have no children.

1 comment:

Arcane Sentiment said...

(cons root ...) is a base case in dataflow, though not in control: it's the part that gets some output without recursing. (And it's the part one forgets at first.)