Asp Forum - Faster Alternatives for Recursion in Ruby -Assignment

Ruby Newbie

9/18/2007 9:49:00 AM

I have the following assignment to be done.I have written the recursive
API and a loop based solution but what is the faster alternative for
these two that can figure into that "fastfunk(n)" method. Thanks for
your help in advance.

Funkonacci Numbers:
Define the Funkonacci numbers as follows:
0 if n < 1
funk(n) = 1 if n = 1
funk(n - 1) - (2 Ã? funk(n - 2)) otherwise

Write a method funk(n) that calculates the nth Funkonacci number
recursively. Generate a few Funkonacci numbers. Now write a second
method, fastfunk(n) that calculates the nth Funkonacci number more
quickly

def funkn(n)
return 0 if n<=0
return 1 if n==1
funkn(n - 1) - (2 * funkn(n - 2))
end
def funknloop(n)
return 0 if n<=0
return 1 if n==1
i1 , i2 = 0,1
for i in 2...(n+1)
num = i2 - 2*i1
i1 ,i2 = i2, num
end
i2
end

puts funkn(10)
puts funknloop(10)
--
Posted via http://www.ruby-....

8 Answers

Peter Hickman

9/18/2007 10:17:00 AM

Ruby Newbie wrote:
> I have the following assignment to be done.I have written the recursive
> API

Whats a "recursive API"? You are talking nonsense here. All you have
done is write a recursive version and an iterative version of a
function. An API is something entirely different.

The first thing you need to do is time your code and prove that one is
faster than the other, on my system they are practically identical.

Marcin Raczkowski

9/18/2007 2:38:00 PM

Ruby Newbie wrote:
> I have the following assignment to be done.I have written the recursive
> API and a loop based solution but what is the faster alternative for
> these two that can figure into that "fastfunk(n)" method. Thanks for
> your help in advance.
>
> Funkonacci Numbers:
> Define the Funkonacci numbers as follows:
> 0 if n < 1
> funk(n) = 1 if n = 1
> funk(n - 1) - (2 Ã? funk(n - 2)) otherwise
>
> Write a method funk(n) that calculates the nth Funkonacci number
> recursively. Generate a few Funkonacci numbers. Now write a second
> method, fastfunk(n) that calculates the nth Funkonacci number more
> quickly
>
> def funkn(n)
> return 0 if n<=0
> return 1 if n==1
> funkn(n - 1) - (2 * funkn(n - 2))
> end
> def funknloop(n)
> return 0 if n<=0
> return 1 if n==1
> i1 , i2 = 0,1
> for i in 2...(n+1)
> num = i2 - 2*i1
> i1 ,i2 = i2, num
> end
> i2
> end
>
> puts funkn(10)
> puts funknloop(10)

I think there was nice acronym for "do your homework yourself" or
something similar

but since I'm doing everything except learn for my final so here it's

to calculate N th fibonacci number

def rfib(n)
return 1 if n<3
rfib(n-1) + rfib(n-2)
end

def ifib(n)
return 1 if n<3
a,b = 1,1
(n-2).times do
a,b = b, a+b
end
b
end

to print all of them along the way: (and here's why iteration one is
much faster - there's no easy way to print them without recalculating
each time)

def rfib(n)
return 1 if n<3
rfib(n-1) + rfib(n-2)
end

10.times do |x|
puts rfib(x+1)
end

def ifib(n)
if n<2
puts "1"
elsif
puts "1\n1"
end

a,b = 1,1
(n-2).times do
a,b = b, a+b
puts b
end
b
end

no coments so you have more fun explaining how you did it on your CE
class :)

Marcin Raczkowski

9/18/2007 2:55:00 PM

Marcin Raczkowski wrote:
> Ruby Newbie wrote:
>> I have the following assignment to be done.I have written the recursive
>> API and a loop based solution but what is the faster alternative for
>> these two that can figure into that "fastfunk(n)" method. Thanks for
>> your help in advance.
>>
>> Funkonacci Numbers:
>> Define the Funkonacci numbers as follows:
>> 0 if n < 1
>> funk(n) = 1 if n = 1
>> funk(n - 1) - (2 Ã? funk(n - 2)) otherwise
>>
>> Write a method funk(n) that calculates the nth Funkonacci number
>> recursively. Generate a few Funkonacci numbers. Now write a second
>> method, fastfunk(n) that calculates the nth Funkonacci number more
>> quickly
>>
>> def funkn(n)
>> return 0 if n<=0
>> return 1 if n==1
>> funkn(n - 1) - (2 * funkn(n - 2))
>> end
>> def funknloop(n)
>> return 0 if n<=0
>> return 1 if n==1
>> i1 , i2 = 0,1
>> for i in 2...(n+1)
>> num = i2 - 2*i1
>> i1 ,i2 = i2, num
>> end
>> i2
>> end
>>
>> puts funkn(10)
>> puts funknloop(10)
>
> I think there was nice acronym for "do your homework yourself" or
> something similar
>
> but since I'm doing everything except learn for my final so here it's
>
> to calculate N th fibonacci number
>
> def rfib(n)
> return 1 if n<3
> rfib(n-1) + rfib(n-2)
> end
>
> def ifib(n)
> return 1 if n<3
> a,b = 1,1
> (n-2).times do
> a,b = b, a+b
> end
> b
> end
>
> to print all of them along the way: (and here's why iteration one is
> much faster - there's no easy way to print them without recalculating
> each time)
>
> def rfib(n)
> return 1 if n<3
> rfib(n-1) + rfib(n-2)
> end
>
> 10.times do |x|
> puts rfib(x+1)
> end
>
> def ifib(n)
> if n<2
> puts "1"
> elsif
> puts "1\n1"
> end
>
> a,b = 1,1
> (n-2).times do
> a,b = b, a+b
> puts b
> end
> b
> end
>
>
> no coments so you have more fun explaining how you did it on your CE
> class :)
>
>
hmm i mistook Funkonacci with Fibonacci numbers and i guess you study on
university of texas ?

how fun :)

anyway:

def rfunk(n)
return 0 if n<1
return 1 if n==1
rfunk(n-1) - 2*rfunk(n-2)
end

def ifunk(n)
return 0 if n<1
return 1 if n==1
a,b = 0,1
(n-1).times do
a,b = b, b-2*a
end
b
end

here's version fur that funky numbers of yours, but if you have to ask
ruby mailing list for such trivial home assigments you probably should
switch curses right now, or mayby peaople in US are just that stupid

Ruby Newbie

9/19/2007 7:04:00 AM

Peter Hickman wrote:
> Ruby Newbie wrote:
>> I have the following assignment to be done.I have written the recursive
>> API
>
> Whats a "recursive API"? You are talking nonsense here. All you have
> done is write a recursive version and an iterative version of a
> function. An API is something entirely different.
>
> The first thing you need to do is time your code and prove that one is
> faster than the other, on my system they are practically identical.

First of all its not function its a method in ruby terms. If you care
too much about terminology better get it rite yourself first
--
Posted via http://www.ruby-....

Ruby Newbie

9/19/2007 7:10:00 AM

Marcin Raczkowski wrote:
> Marcin Raczkowski wrote:
>>> funk(n - 1) - (2 Ã? funk(n - 2)) otherwise
>>> end
>>>
>> def rfib(n)
>> b
>>
>>
>> class :)
>>
>>
> hmm i mistook Funkonacci with Fibonacci numbers and i guess you study on
> university of texas ?
>
> how fun :)
>
> anyway:
>
>
> def rfunk(n)
> return 0 if n<1
> return 1 if n==1
> rfunk(n-1) - 2*rfunk(n-2)
> end
>
> def ifunk(n)
> return 0 if n<1
> return 1 if n==1
> a,b = 0,1
> (n-1).times do
> a,b = b, b-2*a
> end
> b
> end
>
> here's version fur that funky numbers of yours, but if you have to ask
> ruby mailing list for such trivial home assigments you probably should
> switch curses right now, or #mayby peaople in US are just that stupid# Giving racial or personal comments on the members should not be allowed in this forum. Moderators,(If some exists )Please look into this post

To Understand a concept you dont need great problems to solve it cud be
demonstrated in a simple problem. The solution you have given has been
posted by the member already with a for loop.Do you mean using block
over for loop improves the efficiency???????????????

Does using blocks improve it over using 'For'.Please give explanation.

--
Posted via http://www.ruby-....

Peter Hickman

9/19/2007 11:13:00 AM

Ruby Newbie wrote:
> Peter Hickman wrote:
>
>> Ruby Newbie wrote:
>>
>>> I have the following assignment to be done.I have written the recursive
>>> API
>>>
>> Whats a "recursive API"? You are talking nonsense here. All you have
>> done is write a recursive version and an iterative version of a
>> function. An API is something entirely different.
>>
>> The first thing you need to do is time your code and prove that one is
>> faster than the other, on my system they are practically identical.
>>
>
> First of all its not function its a method in ruby terms. If you care
> too much about terminology better get it rite yourself first
>

Well at least you know that much, that does not however excuse the
technobabble of "recursive API". And as for "rite", well you put me in
my place there I can tell you. How about providing the timings or are
you just going to sulk.

Jano Svitok

9/19/2007 12:07:00 PM

On 9/19/07, Ruby Newbie <yeshvanthni@gmail.com> wrote:
> Does using blocks improve it over using 'For'.Please give explanation.

Find out yourself: write both versions and compare them using
Benchmark class (my guess is that they are more or less the same).

Marcin Raczkowski

9/19/2007 1:40:00 PM

Jano Svitok wrote:
> On 9/19/07, Ruby Newbie <yeshvanthni@gmail.com> wrote:
>> Does using blocks improve it over using 'For'.Please give explanation.
>
> Find out yourself: write both versions and compare them using
> Benchmark class (my guess is that they are more or less the same).
>
>

i wrote them more clearly for you, you should see from this that
recursive algorithm uses much more operations - every number have to run
2 threads, and each of thease have to run another 2, that gives you 2^n
method calls, each of them have one arythmetic operation.

where iteration one takes one method call and n*3 arythmetic operations

benchmark for big n should give you clear picture, you can also use
profiler or count method cals and operations. besides, you are CS major
on university, why are you posting your homework here and ask us for
answers than complain we don't give you them ?

comp.lang.ruby

Faster Alternatives for Recursion in Ruby -Assignment

Ruby Newbie

Peter Hickman

Marcin Raczkowski

Marcin Raczkowski

Ruby Newbie

Ruby Newbie

Peter Hickman

Jano Svitok

Marcin Raczkowski

x Login to ForumsZone