Faster Alternatives for Recursion in Ruby -Assignment

[Ruby Newbie]

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)

 

[Peter Hickman]

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]

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]

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]

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

 

[Ruby Newbie]

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.

 

[Peter Hickman]

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]

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]

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 ?