Another common pattern of computation is called tree recursion. As an example, consider computing the sequence of Fibonacci numbers, in which each number is the sum of the preceding two: \[\begin{array}{l} 0, 1, 1, 2, 3, 5, 8, 13, 21, \ldots \end{array}\] In general, the Fibonacci numbers can be defined by the rule \[\begin{array}{lll} \textrm{Fib}(n) & = & \left\{ \begin{array}{ll} 0 & \mbox{if $n=0$}\\ 1 & \mbox{if $n=1$}\\ \textrm{Fib}(n-1)+\textrm{Fib}(n-2) & \mbox{otherwise} \end{array} \right. \end{array}\] We can immediately translate this definition into a recursive procedure function for computing Fibonacci numbers:

Original	JavaScript
(define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2))))))	function fib(n) { return n === 0 ? 0 : n === 1 ? 1 : fib(n - 1) + fib(n - 2); }

Original		JavaScript
Figure 1.9 The tree-recursive process generated in computing (fib 5).		Figure 1.10 The tree-recursive process generated in computing fib(5).

Consider the pattern of this computation. To compute (fib 5), fib(5), we compute (fib 4) fib(4) and (fib 3). fib(3). To compute (fib 4), fib(4), we compute (fib 3) fib(3) and (fib 2). fib(2). In general, the evolved process looks like a tree, as shown in figure 1.9. figure 1.10. Notice that the branches split into two at each level (except at the bottom); this reflects the fact that the fib procedure function calls itself twice each time it is invoked.

This procedure function is instructive as a prototypical tree recursion, but it is a terrible way to compute Fibonacci numbers because it does so much redundant computation. Notice in figure 1.9 figure 1.10 that the entire computation of (fib 3)—almost half the work—is fib(3)—almost half the work—is duplicated. In fact, it is not hard to show that the number of times the procedure function will compute (fib 1) fib(1) or (fib 0) fib(0) (the number of leaves in the above tree, in general) is precisely $\textrm{Fib}(n+1)$. To get an idea of how bad this is, one can show that the value of $\textrm{Fib}(n)$ grows exponentially with $n$. More precisely (see exercise 1.13), $\textrm{Fib}(n)$ is the closest integer to $\phi^{n} /\sqrt{5}$, where \[\begin{array}{lllll} \phi&=&(1+\sqrt{5})/2 & \approx & 1.6180 \end{array}\] is the golden ratio, which satisfies the equation \[\begin{array}{lll} \phi^{2} &=&\phi + 1 \end{array}\] Thus, the process uses a number of steps that grows exponentially with the input. On the other hand, the space required grows only linearly with the input, because we need keep track only of which nodes are above us in the tree at any point in the computation. In general, the number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree.

We can also formulate an iterative process for computing the Fibonacci numbers. The idea is to use a pair of integers $a$ and $b$, initialized to $\textrm{Fib}(1)=1$ and $\textrm{Fib}(0)=0$, and to repeatedly apply the simultaneous transformations \[\begin{array}{lll} a & \leftarrow & a+b \\ b & \leftarrow & a \end{array}\] It is not hard to show that, after applying this transformation $n$ times, $a$ and $b$ will be equal, respectively, to $\textrm{Fib}(n+1)$ and $\textrm{Fib}(n)$. Thus, we can compute Fibonacci numbers iteratively using the procedure function

Original	JavaScript
(define (fib n) (fib-iter 1 0 n)) (define (fib-iter a b count) (if (= count 0) b (fib-iter (+ a b) a (- count 1))))	function fib(n) { return fib_iter(1, 0, n); } function fib_iter(a, b, count) { return count === 0 ? b : fib_iter(a + b, a, count - 1); }

This second method for computing $\textrm{Fib}(n)$ is a linear iteration. The difference in number of steps required by the two methods—one linear in $n$, one growing as fast as $\textrm{Fib}(n)$ itself—is enormous, even for small inputs.

One should not conclude from this that tree-recursive processes are useless. When we consider processes that operate on hierarchically structured data rather than numbers, we will find that tree recursion is a natural and powerful tool.[1] But even in numerical operations, tree-recursive processes can be useful in helping us to understand and design programs. For instance, although the first fib procedure function is much less efficient than the second one, it is more straightforward, being little more than a translation into Lisp JavaScript of the definition of the Fibonacci sequence. To formulate the iterative algorithm required noticing that the computation could be recast as an iteration with three state variables.

Example: Counting change

It takes only a bit of cleverness to come up with the iterative Fibonacci algorithm. In contrast, consider the following problem: How many different ways can we make change of \$1.00, $1.00 (100 cents), given half-dollars, quarters, dimes, nickels, and pennies (50 cents, 25 cents, 10 cents, 5 cents, and 1 cent, respectively)? More generally, can we write a procedure function to compute the number of ways to change any given amount of money?

This problem has a simple solution as a recursive procedure. function. Suppose we think of the types of coins available as arranged in some order. Then the following relation holds:

The number of ways to change amount $a$ using $n$ kinds of coins equals

• the number of ways to change amount $a$ using all but the first kind of coin, plus
• the number of ways to change amount $a-d$ using all $n$ kinds of coins, where $d$ is the denomination of the first kind of coin.

To see why this is true, observe that the ways to make change can be divided into two groups: those that do not use any of the first kind of coin, and those that do. Therefore, the total number of ways to make change for some amount is equal to the number of ways to make change for the amount without using any of the first kind of coin, plus the number of ways to make change assuming that we do use the first kind of coin. But the latter number is equal to the number of ways to make change for the amount that remains after using a coin of the first kind.

Thus, we can recursively reduce the problem of changing a given amount to problems of changing smaller amounts or using fewer kinds of coins. Consider this reduction rule carefully, and convince yourself that we can use it to describe an algorithm if we specify the following degenerate cases:[2]

• If $a$ is exactly 0, we should count that as 1 way to make change.
• If $a$ is less than 0, we should count that as 0 ways to make change.
• If $n$ is 0, we should count that as 0 ways to make change.

We can easily translate this description into a recursive procedure: function:

Original

JavaScript

(define (count-change amount) (cc amount 5)) (define (cc amount kinds-of-coins) (cond ((= amount 0) 1) ((or (< amount 0) (= kinds-of-coins 0)) 0) (else (+ (cc amount (- kinds-of-coins 1)) (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins))))) (define (first-denomination kinds-of-coins) (cond ((= kinds-of-coins 1) 1) ((= kinds-of-coins 2) 5) ((= kinds-of-coins 3) 10) ((= kinds-of-coins 4) 25) ((= kinds-of-coins 5) 50)))

function count_change(amount) { return cc(amount, 5); } function cc(amount, kinds_of_coins) { return amount === 0 ? 1 : amount < 0 || kinds_of_coins === 0 ? 0 : cc(amount, kinds_of_coins - 1) + cc(amount - first_denomination(kinds_of_coins), kinds_of_coins); } function first_denomination(kinds_of_coins) { return kinds_of_coins === 1 ? 1 : kinds_of_coins === 2 ? 5 : kinds_of_coins === 3 ? 10 : kinds_of_coins === 4 ? 25 : kinds_of_coins === 5 ? 50 : 0; }

(The first-denomination procedure first_denomination function takes as input the number of kinds of coins available and returns the denomination of the first kind. Here we are thinking of the coins as arranged in order from largest to smallest, but any order would do as well.) We can now answer our original question about changing a dollar:

Original	JavaScript
(count-change 100) 292	count_change(100); 292

Count-change The function count_change generates a tree-recursive process with redundancies similar to those in our first implementation of fib. (It will take quite a while for that 292 293 to be computed.) On the other hand, it is not obvious how to design a better algorithm for computing the result, and we leave this problem as a challenge. The observation that a tree-recursive process may be highly inefficient but often easy to specify and understand has led people to propose that one could get the best of both worlds by designing a smart compiler that could transform tree-recursive procedures functions into more efficient procedures functions that compute the same result.[3]

Exercise 1.11 A function $f$ is defined by the rule that rules $f(n)=n$ if $n < 3$ and $f(n)={f(n-1)}+2f(n-2)+3f(n-3)$ if $n\ge 3$. Write a procedure JavaScript function that computes $f$ by means of a recursive process. Write a procedure function that computes $f$ by means of an iterative process.

Solution

// iterative function function f_iterative(n) { return n < 3 ? n : f_iterative_impl(2, 1, 0, n - 2); } function f_iterative_impl(a, b, c, count) { return count === 0 ? a : f_iterative_impl(a + 2 * b + 3 * c, a, b, count - 1); } //recursive function function f_recursive(n) { return n < 3 ? n : f_recursive(n - 1) + 2 * f_recursive(n - 2) + 3 * f_recursive(n - 3); }

Exercise 1.12 The following pattern of numbers is called Pascal's triangle. \[ { \begin{array}{rrrrcrrrr} & & & & 1 & & & & \\ & & &1 & &1 & & & \\ & &1 & & 2 & &1 & & \\ &1 & &3 & &3 & &1 & \\ 1 & & 4 & & 6 & & 4 & & 1 \\ & & & & \ldots & & & & \end{array}} \] The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it.[4] Write a procedure function that computes elements of Pascal's triangle by means of a recursive process.

Solution

Original	JavaScript
	function pascal_triangle(row, index) { return index > row ? false : index === 1 || index===row ? 1 : pascal_triangle(row - 1, index - 1) + pascal_triangle(row - 1, index); }

Exercise 1.13 Prove that $\textrm{Fib}(n)$ is the closest integer to $\phi^n/\sqrt{5}$, where $\phi= (1+\sqrt{5})/2$.

Original		JavaScript
Hint: Let $\psi= (1-\sqrt{5})/2$. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that $\textrm{Fib}(n)=(\phi^n-\psi^n)/\sqrt{5}$.		Hint: Use induction and the definition of the Fibonacci numbers to prove that $\textrm{Fib}(n)=(\phi^n-\psi^n)/\sqrt{5}$, where $\psi= (1-\sqrt{5})/2$.

Solution

First, we show that $\textrm{Fib}(n) = \dfrac{\phi^n-\psi^n}{\sqrt{5}}$, where $\psi = \dfrac{1-\sqrt{5}}{2}$ using strong induction.
$\textrm{Fib}(0) = 0$ and $\dfrac{\phi^0-\psi^0}{\sqrt{5}} = 0$
$\textrm{Fib}(1) = 1$ and $\dfrac{\phi^1-\psi^1}{\sqrt{5}} = \dfrac{\dfrac{1}{2}\left(1+\sqrt{5} - 1 + \sqrt{5}\right)}{\sqrt{5}} = 1$
So the statement is true for $n=0,1$. Given $n \geq 1$, assume the proposition to be true for $0, 1, \dots , n$.
$\textrm{Fib}(n+1) = \textrm{Fib}(n) + \textrm{Fib}(n-1) = \dfrac{\phi^n-\psi^n + \phi^{n-1} - \psi^{n-1}}{\sqrt{5}}$
$= \dfrac{\phi^{n-1}(\phi + 1) - \psi^{n-1}(\psi + 1)}{\sqrt{5}}$
$=\dfrac{\phi^{n-1}(\phi^2) - \psi^{n-1}(\psi^2)}{\sqrt{5}} = \dfrac{\phi^{n+1} - \psi^{n+1}}{\sqrt{5}}$, so the statement is true.
Notice that since $|\psi| < 1$ and $\sqrt{5} > 2$, one has $\left|\dfrac{\psi^n}{\sqrt{5}}\right| < \dfrac{1}{2}$
Then the integer closest to $\textrm{Fib}(n) + \dfrac{\psi^n}{\sqrt{5}} = \dfrac{\phi^n}{\sqrt{5}}$ is $\textrm{Fib}(n)$.