M11: Mutual Recursion

f applies g and g applies f:

Each of these definitions follows from the observations that an even number is one more than an odd number, and so on.

These functions are mutually recursive because is-even? applies is-odd? and is-odd? applies is-even?.

This is the defining feature of mutual recursion.

There are lots of ways to write is-even?, most of which do not involve mutual recursion. Mutual recursion is obviously not required to solve this problem. But this solution does show, in just a few lines of code, what a typical mutually recursive solution looks like. When we get to general trees, mutual recursion will be a frequently used friend.

Need a hint? Return to where we first introduced mutual recursion in M09.

This was the missing piece in the aside on mergesort .

;; (mergesort lst) puts lst in increasing order
;; mergesort: (listof Num) -> (listof Num)
(define (mergesort lst)
  (cond [(empty? lst) empty]
        [(empty? (rest lst)) lst]
        [else (merge (mergesort (keep-alternates lst))
                     (mergesort (drop-alternates lst)))]))

;; Closed-box tests:
(check-expect (mergesort (list 4 7 3 0 1 9 5 2 6 8)) (list 0 1 2 3 4 5 6 7 8 9))

keep-alternates and drop-alternates are mutally recursive. Each one applies the other in classic mutual recursion style:

This example is from the end of Module 10 .

We slipped in mutual recursion dressed as a helper function! eval applies eval-binode and eval-binode applies eval in classic mutual recursion style.

The template uses mutual recursion: binexp-template applies binode-template and binode-template applies binexp-template.