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:
\[ 0, 1, 1, 2, 3, 5, 8, 13, 21, \ldots \]
In general, the Fibonacci numbers can be defined by the rule
\begin{eqnarray*}
\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{eqnarray*}

We can immediately translate this definition into a recursive function for computing Fibonacci numbers:

function fib(n) { return n === 0 ? 0 : n === 1 ? 1 : fib(n - 1) + fib(n - 2); }

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

This
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.5 that
the entire computation of
`fib(3)`—almost half the work—is
duplicated. In fact, it is not hard to show that the number of times
the function will compute `fib(1)` or `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
\[ \phi=(1+\sqrt{5})/2\approx 1.6180 \]
is the
*golden ratio*, which satisfies the equation
\[ \phi^{2} =\phi + 1 \]
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{eqnarray*} a & \leftarrow & a+b \\ b & \leftarrow & a \end{eqnarray*} 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 function

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); }

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`
function
is much less efficient than the second one, it is more
straightforward, being little more than a translation into
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 names.

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$, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a function to compute the number of ways to change any given amount of money?

This problem has a simple solution as a recursive 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 function:

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`
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:

count_change(100);

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 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
functions
into more efficient
functions
that compute the same result.[3]

// 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); }

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); }

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

[1] An example of this was hinted
at in section 1.1.3:
The interpreter itself evaluates expressions
using a tree-recursive process.

[2] For example, work through in detail how the
reduction rule applies to the problem of making change for 10 cents
using pennies and nickels.

[3] One
approach to coping with redundant computations is to arrange matters
so that we automatically construct a table of values as they
are computed. Each time we are asked to apply the
function
to some argument, we first look to see if the value is already stored in the
table, in which case we avoid performing the redundant computation.
This strategy, known as
*tabulation* or *memoization*, can be
implemented in a straightforward way. Tabulation can sometimes be
used to transform processes that require an exponential number of
steps (such as `count-change`)
into processes whose space and time
requirements grow linearly with the input. See
exercise 3.27.

[4] The elements of Pascal's triangle are
called the *binomial coefficients*, because the
$n$th row consists of
the coefficients of the terms in the
expansion of $(x+y)^n$. This
pattern for computing the coefficients
appeared in Blaise Pascal's 1653 seminal work on
probability theory,
*Traité du triangle arithmétique*.
According to
Knuth (1973), the same pattern appears in the *Szu-yuen
Yü-chien* (

The Precious Mirror of the Four Elements), published by the Chinese mathematician Chu Shih-chieh in 1303, in the works of the twelfth-century Persian poet and mathematician Omar Khayyam, and in the works of the twelfth-century Hindu mathematician Bháscara Áchárya.

1.2.2 Tree Recursion