factorial and fibonacci functions

[CodeMonkey2000]

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

[Cervantes]

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,

[Catalyst]

fibonacci doesnt require recursion

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

[Clayton]

OMG its Catalyst :O hes back!!! YAY all hail Catalyst