From: Glenn Cadman Date: 2006-07-14T17:32:27+09:00 Subject: Re: Recursion and Ruby Daniel Martin wrote: > "Erik Veenstra" writes: > >> You could use "case" as well (see version 2). It's faster. >> Using an ordinary if..else (without the elsif part) is faster >> (see version 3). And version 4 is once again faster. >> >> 4 is faster than 3 is faster than 2 is faster than 1... > > All of these suffer from the problem that they make approximately fib(n) > function calls to compute fib(n). Why not remember the value of > fib(n) the ruby way, with a Hash that computes it naturally? > > $fib = Hash.new{|h,k| h[k] = h[k-2] + h[k-1]} > $fib[0] = 0 > $fib[1] = 1 > > def fib(n) > $fib[n] > end > > This will be faster, and O(n), rather than O(fib(n)). Also note that > the base cases of 0 and 1 are handled simply and declaratively without > messing up the main body of the code. > > (Of course, now someone will respond with one of the O(log(n)) > algorithms for computing fib(n)) Well whilst my orginal exercise was just to get recursion working in ruby, I have to say this solution is very quick to calculate any result and is recursive in a way that is quite "foriegn" to me. The problem for me is that I find it difficult to understand what is happening in this code. I would have though the stack would collapse due to referencing something that is not defined yet. eg. h[k-2] for example in the intial state of the $fib hash would not be found unless the k was 3 or 2. eg $fib(30) would return "I dont have any thing to reference for h[30] = h[28] + h[29], has h[28] and h[29] havent been defined. BTW How would I then access $fib to puts an output of the sequence eg. 0 1 1 2 3 5 8 13 etc. -- Posted via http://www.ruby-forum.com/.