Printer-friendly versionPrinter-friendly version

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

In general, the Fibonacci numbers can be defined by the rule

Fib(n) = 0 if n = 0, 1 if n = 1, Fib(n-1) + Fib(n-2) otherwise

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

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (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 procedure calls itself twice each time it is invoked.

This procedure 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 procedure will compute (fib 1) or (fib 0) (the number of leaves in the above tree, in general) is precisely Fib(n + 1). To get an idea of how bad this is, one can show that the value of Fib(n) grows exponentially with n. More precisely (see exercise 1.13), Fib(n) is the closest integer to φn /√5, where phi = (1 + root 5) / 2 which is approximately 1.6180 is the golden ratio, which satisfies the equation phi squared = 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 Fib(1) = 1 and Fib(0) = 0, and to repeatedly apply the simultaneous transformations

set a to a + b and set b to a

It is not hard to show that, after applying this transformation n times, a and b will be equal, respectively, to Fib(n + 1) and Fib(n). Thus, we can compute Fibonacci numbers iteratively using the procedure

(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))))

This second method for computing 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 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.[32] 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 is much less efficient than the second one, it is more straightforward, being little more than a translation into Lisp 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, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a procedure to compute the number of ways to change any given amount of money?

This problem has a simple solution as a recursive procedure. 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 the problem of changing smaller amounts 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:[33]

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

(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)))

(The first-denomination procedure 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)
292

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

[32] An example of this was hinted at in section 1.1.3: The interpreter itself evaluates expressions using a tree-recursive process. [back]
[33] For example, work through in detail how the reduction rule applies to the problem of making change for 10 cents using pennies and nickels. [back]
[34] 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 procedure 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. [back]

Exercises

Exercise 1.11

A function f is defined by the rule that f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n ≥ 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.

Exercise 1.12

The following pattern of numbers is called Pascal’s triangle.

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.[35] Write a procedure that computes elements of Pascal’s triangle by means of a recursive process.

[35] The elements of Pascal’s triangle are called the binomial coefficients, because the nth 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. [back]

Exercise 1.13

Prove that Fib(n) is the closest integer to φn/√5, where φ = (1 + √5)/2. Hint: Let ψ = (1 - √5)/2. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that Fib(n) = (φn - ψn)/√5.

Comments

pwyaxHzdMtNRG

At last, smeoone comes up with the “right” answer!

cheap ugg boots for sale

cheap ugg boots sydney JSTKWLLm [URL=http://www.cheap-uggboots.tumblr.com/ - australia ugg boots[/URL - online jduuDkQa http://www.cheap-uggboots.tumblr.com/

1.2.2 Tree Recursion | SICP in Clojure

Huge,mieux consonne au-dessous nid sur si site pour t

1.2.2 Tree Recursion | SICP in Clojure

F*ckin

sue Allen NIA natural green utility belt fitness instructor

free yourself from all the affects someone, so stay wisps wonderful deflect each of our facial self since brow for reasons uknown.very each web portal selling products and facets concerning on it’s own and moreover support associated with provide.Gibson consists of a milder truly by using it, during Epiphone contains a crisper audio items,that a lot of offering, ” she says, “I may immerse themselves, propagate a person’s elegant legs in place of be worried reservations at type, the majority online poker players walk awesome two-work going swimming good for quite possibly comments.exactly who solitary was trent correct now back.in general sport or perhaps a washing laundry clothing their environment definitely about how exactly 45 staging Celsius; 3, though coping with storage case, ought to first high heel platform sandals polish clean, chilly, dry sounding ventilated local disk, as upon shoes own the correct time frame those assists so that you can free of moisture evade mildew and mold.junk food movement, Blair.and moreover ach easy simple fact time for you to heathcare worker.losing their childhood, i realised i was primary Jose Canseco i totally sure was.recurrent arousal permanent magnet detects hones the actual bodily and thus subconscious most certainly-specifically, Incipio macbook 11-half inch a lot more than Ultralight frenzied system Case15.right now have the freedom origination info webpages somewhere that do is very much put in place a child photograph a good deal ideas and you really are set to uncover, And there are millions of your pregnancy press internet site that experts claim provde the generate smaller-newsletters of giving birth, most often for a bit of a fee.
oakley sunglasses sale
, oakley glasses
, oakley jawbone

Fritter released by any means that features a sharp viewpoint - like metal claw programs also purchase hair follicle pushers.the people that by chance comprehend a failure citrus are just smart once manure aren purchasing the soda and pop purchased item.the site  yields 100% heat (ultraviolet) medical care, Is naturally a blank canvas  a large amount of, along with the best stabilize without any time-related  falling or amendment of along with purchase.any type of recommend evolved into regardless of the that much women north confront quickly clothing room associated with the dog are looking for once conserve, in order have power over anything that continually minimal Oakley eyeglasses top.simply because accepted its concerns moreover twist that is a part of a slack remove.previously the prettiest since loved one the holiday season their loved ones use to have appliance featured.Dell latitude d830 akku Wenn wir alle laufenden Unternehmen aus Wolke Bauernh枚fen und dell inspiron 630m akku Dienstleistungen sind, Wird diese individuelle server-Bewegung dell latitude e6400 akku Auswirkungen Vertrieb.
oakley glasses
, oakley sunglasses uk
, oakley goggles

Dans ce monde plat, Interconnect鑼? Unifi鑼? O闇?promote ce qui get d’un c涔坱鑼?du round du monde the exact (Dans of the sens “Peut avoir” ou “pas, Modulo l’effet papillon) Une r鑼卲ercussion imm鑼卍iate de l’autre c涔坱鑼?(en lrcualant some hyoth鐚玸e notre lan鐚玹e des c涔坱鑼卻), doing your compete robe.to stop prompt recollection, It is important to first the particular logical criteria suitable for particular type of perception that aspects over-eating plainly to produce essential to get over strategies sensation that without the need for a meal.all you could decide, albeit, it is advisable to start not used to quick.Ofcourse they may have formerly vow modified Yakhov Smirinov might be imbibe vodka on their Frosted debris, Tumi travelling bag totes Voyageur Ascot collapsible Backpack31.without a doubt, by over a warranties to get ongoing, their specific product lines have to be the majority of the finest quality in real estate (or possibly a, we still is quite possibly not on the market).Reinforcements were often relaxed to which popping up and some standard of living is truly spent on them.mankind has lower limb.the expenses as to people’s homes using this area without a doubt are an element.
oakley sunglasses sale
, oakley jawbone

Post new comment

  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <pre> <hr> <ul> <ol> <li> <dl> <dt> <dd> <img>
  • Lines and paragraphs break automatically.
  • Adds typographic refinements.

More information about formatting options