From: Jeffrey Schwab <jeff@...>
Date: 2005-12-17T12:57:45+09:00
Subject: Re: ruby beats them all

Matt O'Connor wrote:
> jwesley wrote:
> 
>> If Ruby properly handled tail-recursion, then the "accumulator passing"
>> style work for any number:
>>
>> def fib n
>>   fib_helper( n, 1, 1)
>> end
>>
>> def fib_helper n, next_val, val
>>   n < 1 ? val : fib_helper( n-1, next_val + val, next_val)
>> end
>>
>> the above code (in accumulator-passing style) only works through about
>> n=1300 for me.
> 
> 
> Though a more "functional approach" is to hide the helper function:
> 
> def fib n
>   def fib_helper n, next_val, val
>     n < 1 ? val : fib_helper( n-1, next_val + val, next_val)
>   end
>   fib_helper( n, 1, 1)
> end

An alternative implementation might even use only one subroutine.

def fib n, p1 =1, p2 =1
	n < 1 ? p2 : fib( n - 1, p1 + p2, p1 )
end