[plt-scheme] Dr.Scheme freezes on (fib 100) recursion

Do you realize how many times your version of procedure fib is called for 
(fib 100)?

Here is a version that is linear in n. (although for very large n, f1 and f2 
become so large that (+ f0 f1) is going to take more time for each next 
step)

#lang scheme

(define (make-fib f0 f1)
 (define (fib n)
  (define (fib n f1 f2)
   (if (= n 2) f2
    (fib (- n 1) f2 (+ f1 f2))))
  (case n
   ((0) f0)
   ((1) f1)
   (else (fib n f1 (+ f0 f1)))))
 fib)

(define fib (make-fib 1 1))

(time (fib 99))
(time (fib 100))
(time (fib 10000))

#|
Welcome to DrScheme, version 4.1.3.8-svn6jan2009 [3m].
Language: Module; memory limit: 1000 megabytes.
cpu time: 0 real time: 0 gc time: 0
354224848179261915075
cpu time: 0 real time: 0 gc time: 0
573147844013817084101
cpu time: 16 real time: 16 gc time: 0
54438373113565281338734260993750380135389184554695967026247715841208582865622349017083051547938960541173822675978026317384359584751116241439174702642959169925586334117906063048089793531476108466259072759367899150677960088306597966641965824937721800381441158841042480997984696487375337180028163763317781927941101369262750979509800713596718023814710669912644214775254478587674568963808002962265133111359929762726679441400101575800043510777465935805362502461707918059226414679005690752321895868142367849593880756423483754386342639635970733756260098962462668746112041739819404875062443709868654315626847186195620146126642232711815040367018825205314845875817193533529827837800351902529239517836689467661917953884712441028463935449484614450778762529520961887597272889220768537396475869543159172434537193611263743926337313005896167248051737986306368115003088396749587102619524631352447499505204198305187168321623283859794627245919771454628218399695789223798912199431775469705216131081096559950638297261253
84824200789710905475402843814961193046506186617012298328896435273375079278606944476185352514442107792804597990456129812942380915605503303233891960916223669875992278292319189668801771857555552099465332012844650237115371514174929091310489720345557750719664542523286202201950609148358522388271101670843305116994211577515125551025165593188816404834412955703882547752111157739578011586839707260256561482495646053870028033131186148539980539703155572752969339958607985038158144627643385882852953580342485084542644647168153100153318047956743639681565332615250957112748041192819602214884914828438912417852017450730553892871785792350941774338333150689823935442198880542933244037119486721554357654856549913451927109891980266518456492782782721295764924023550759555820564756936539487331765900020637312657064350970948264971003873351747771340331902810557566793178947002411880309460403436295347199746139227479154973035641263307423082405199999610154978466734045832685296038830112076562924599813625165234709396304973
4046445106365304163630823669242257761468288461791843224793434406079917883360676846711185597501
> |#


Jos

----- Original Message ----- 
From: "John Clements" <clements at brinckerhoff.org>
To: "Richard Cleis" <rcleis at mac.com>
Cc: <laalaalovesu at yahoo.com>; <plt-scheme at list.cs.brown.edu>
Sent: Thursday, January 08, 2009 8:46 AM
Subject: Re: [plt-scheme] Dr.Scheme freezes on (fib 100) recursion


> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>