Changeset 8965 in project


Ignore:
Timestamp:
02/25/08 18:33:28 (12 years ago)
Author:
graham
Message:

Changes applied for graham (137.207.200.153) through svnwiki:

more on tail recursion.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • wiki/chicken-for-ruby-programmers

    r8804 r8965  
    282282    (sqrt (* a a) (* b b)))
    283283</enscript>
     284==== Recursion and tail-call optimization
    284285
    285286In Scheme, recursion is a very important tool.  In fact, it is so
     
    315316  49995000
    316317
     318Note the {{+}} in front of the {{(add-up-to (sub1 ...))}}. That is a cue that this is not tail-recursive code: each level of recursion must eventually come back 'up a level' in order to complete the addition, and so the program must keep a live reference to every level of recursion until the final result is computed.
     319
    317320In most other Schemes, however, this will break just like in Ruby,
    318321because when the {{(+ (add-up-to (sub1 x)) x)}} expression is
     
    320323frame so that when it returns the x can be added to the result.
    321324
    322 [Note that this code will 'break' in Chicken too, but only for much
     325[This code will 'break' in Chicken too, but only for much
    323326larger numbers. Although Chicken doesn't have an arbitrary stack
    324327depth, if you try (add-up-to) on a large enough number, you'll use up
     
    332335be optimized to become a ''goto'', replacing the current stack frame.
    333336
    334 Ruby still can't handle it:
     337Here is a tail-recursive version. Ruby still can't handle it:
    335338
    336339  irb(main):027:0> def add_up_to(x)
     
    348351  SystemStackError: stack level too deep
    349352
    350 Scheme (this works in all Schemes):
     353But Scheme can (this works in all Schemes):
    351354
    352355  #;2> (define (add-up-to x)
     
    360363  #;4> (add-up-to 9999)
    361364  49995000
     365
     366Note that the recursive call to {{inner}} isn't nested inside another function call, such as the {{(+ (add-up-to ...))}} in the first version. This is the hallmark of a tail-recursive program. (The astute reader might note that it actually *is* nested inside an {{(if ...)}} procedure, but conditional forms like {{if}} are handled intelligently in tail-recursion. The {{if}} statement itself is not nested inside a procedure call, so all is well.)
    362367
    363368As you'll notice, this version is a lot faster in Chicken too because
Note: See TracChangeset for help on using the changeset viewer.