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.
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)))
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,
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
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.
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.