Computer Science Canada :: View topic - factorial and fibonacci functions

Computer Science Canada

factorial and fibonacci functions

Author:

CodeMonkey2000 [ Mon Aug 07, 2006 9:27 pm ]

Post subject:

factorial and fibonacci functions

code:

fcn factorial (x : int) : int

if x <= 1 then
result 1 %base case
else
result
x * factorial (x - 1) %recursive case
end if

end factorial

var k : int := 5

for x : 1 .. 10

k := factorial (x)
put x, "!=", k

end for

this program shows how factorials can be done within a function, by using recursive functions. this code out puts the factorials of 1-10.
this is what the function factorial does if the argument is 5:

code:

5
|
5*4!
|
4*3!
|
3*2!
|
2*1!
|
1

code:

fcn fibonacci (x : int) : int

if x = 0 or x = 1 then %base case
result x
else
result fibonacci (x - 1) + fibonacci (x - 2) %recursive case
end if

end fibonacci

for x : 1 .. 35

put fibonacci (x)

end for

another recursive function. this time it does fibonacci.
the fibonacci series.
0,1,1,2,3,5,8,13,21...
it begins with 0 and 1 and has the property that each subsequebt fibonacci number is the sum of the previous two fibonacci numbers.

0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
n ???

this program basiclly finds the Nth fibonacci
heres how the function works (very roughly) with the 3rd fabonici(sp i know)

code:

f(3)
|
result f(2) + f(1)
/ \
result f(1) + f(0) result 1
| |
result 1 result 0

Author:

Cervantes [ Mon Aug 07, 2006 9:55 pm ]

Post subject:

Good stuff. That's the basic recursion solution to these problems. But you can optimize it a lot.

Consider only your factorial program. The same concepts will apply to the Fib numbers.

The following loop is very inefficient:

code:

var k : int := 5

for x : 1 .. 10

k := factorial (x)
put x, "!=", k

end for

It is inefficient because to get 4! you multiply 1*2*3*4. To get 5!, all you should need is 5*4!, as your little description says. We've already calculated 4! from the previous loop. But with this code, your function will do all that multiplication again.

The solution is to memorize what 4! was when it comes time to calculate 5!. Create an array of factorials. When you need to get a factorial that isn't in your array, expand that array (using the previous elements in that array) until you've expanded it far enough and can answer the initial question (what is the factorial of x, where x is some number larger than the upper() of your array of factorials?).

Actually, I just did this in Ruby for a Project Euler question. Here's the code:

Ruby:

class Fixnum
@@facts = [1]
def fact
return @@facts[self] if self >= 0 and self < @@facts.length
@@facts.length.upto(self) do |i|
@@facts[i] = @@facts[i-1] * i
end
@@facts[self]
end
end

A handle preceeded by "@@" is a class variable.

This little code snippet allows us to write things like,

Ruby:

68.fact

and it will be calculated. Then if we were to say

Ruby:

68.fact
67.fact

Nothing new would be calculated, because it's already been memoized.

P.S. Dan, syntax highlighting has a minor bug. If your code contains a "[i ]" (minus space) then italics will be screwed up in the text afterwards. You won't get any italics until a [/i] is found. After that [/i], the size of the text appears larger, as it does in this post.

Author:

Catalyst [ Wed Aug 09, 2006 11:36 am ]

Post subject:

fibonacci doesnt require recursion Very Happy

code:

const Phi := 1.618033989
const isqrt5 := 1 / sqrt (5)
fcn fibonacci (n : int) : int
result round (((Phi) ** n - (-1 / Phi) ** n) * isqrt5)
end fibonacci
for i : 1 .. 20
put fibonacci (i)
end for

Author:	Clayton [ Wed Aug 09, 2006 2:08 pm ]
Post subject:
OMG its Catalyst :O hes back!!! YAY all hail Catalyst

You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy