Tree recursion is a common pattern in computation. The number of steps required for a tree-recursive process is proportional to the number of nodes in the tree, and the space required is proportional to the maximum depth.

Exercise 1.11

A recursive and iterative implementation of f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n> 3 can be written as:

; recursive
(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1))
         (* 2 (f (- n 2)))
         (* 3 (f (- n 3))))))

; iterative
(define (g n)
  (define (g-iter a b c count)
    (if (< count 3)
        a
        (g-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))
  (if (< n 3)
      n
      (g-iter 2 1 0 n)))

In the f procedure we recurse into each branch, even when we have already gotten the value before. The definition is straightforward and easy to translate.

The magic in the interative procedure g is using a as an acumulator, and passing a->b and b->c. This keeps the representations of each recursive branch previously calculated. The iteration stops when the counter is lower than 3 and then returns the value of a.

Exercise 1.12

Computing an element of Pascal's triangle translates into a simple tree-recursive procedure.

(define (pascal-el row col)
  (cond ((< row col) 0)
        ((< col 0) 0)
        ((= row 0) 1)
        (else (+ (pascal-el (- row 1) (- col 1))
                 (pascal-el (- row 1) col)))))

Using elements with a zero-based index the 0th row is always going to be 1. If the column is less than zero then we are outside of the triangle. Likewise each row adds one more element than the last row. If the column is greater than the row, then we are outside of the triangle. Otherwise the value of any element inside the triangle is the sum of the two elements above it.

Exercise 1.13

My math skills are wretched. I had no clue where to start after staring at the book for 20 mins and a little googling on inducive proofs. Please read see the solutions from Ken Dyck or Bill the Lizard. Both have formatted their answers for easy reading.