Design Pattern: Nested Tree Recursion

An alternate pattern for binary tree recursion is similar to tail recursion on lists, nesting two recursive function calls:

(define (myfun tree)
         (myfunb tree initanswer))

(define (myfunb tree answer)
         (if (pair? tree)
                 (myfunb (cdr tree)
                         (myfunb (car tree) answer))
                 (combine answer (baseanswer tree))))

Example: Count the symbols in a tree structure:

(define (nsymbols tree) (nsymbolsb tree 0))

(define (nsymbolsb tree n)
  (if (pair? tree)
      (nsymbolsb (cdr tree)
                 (nsymbolsb (car tree) n))
      (+ n (if (symbol? tree) 1 0)) ) )

Contents    Page-10    Prev    Next    Page+10    Index