# Top coder

The programmer, like the poet, works only slightly removed from pure though-stuff. He builds his castles int he air, from air, creating by exertion of the imagination.

— Frederick P. Brooks.

The programmer, like the poet, works only slightly removed from pure though-stuff. He builds his castles int he air, from air, creating by exertion of the imagination.

— Frederick P. Brooks.

Advertisements

Tonight, I write some code in LISP for my homework. One of these was working with function definition, and fibonacci function was chosen as my example on this stuff.

In LISP, I wrote something like :

(defun fibo ( N )

( if ( or ( = 0 N ) ( = 1 N)) 1

(+ (fibo ( 1- N)) (fibo (1- ( 1- N)))

)))

Wow, with n = 5000, my laptop was freezing LOL.

So, I find some smarter way to solve this problem.

This time, I choose Python (my favourite ) as my ‘weapon’.

**Let’s dig into this problem:**

Fibonacci problem is defined on a non-negative integer number N:

if n is equal to 1 or 0 :

return 1

else

return fibonacci(N -1 ) + fibonacci( N-2)

I’m gonna make this clearer with following expanding:

if N = 0 or N = 1 : reuturn 1 ( clear, nothing to say)

if N = 2 : return f(0 ) + f(1)

if N = 3 : return f(2 ) + f(1) = [f(0 ) + f(1)] + f(1)

if N =4 : return f(3) + f(2) = {[f(0 ) + f(1)] + f(1)} + [f(0) + f(1)]

……… etc..

OK, that’s enough expanding, from this point , we are able to form a line ( or a pattern ) of this kind of recursive rule.

For computing the n-th fibonacci number, we don’t have to make any recursive call. Instead, we could sum up a series of numbers – each of them was computed by adding cumulatively numbers – until we meet the basic cases ( o and 1).

And each call in this series need to know 2 previous values ( f(N-1 ) and f(N-2)) , so we save these 2 values for present call.

That’s the idea, and here is the code (in Python – I’m sure it’s very clear, very ‘natural’ to your mind):

# fibo problem in a smart way def fibo (n): fn1 = 1 # f(n-1 ) fn2 = 1 # f(n-2 ) S = 0 count = 2; if n == 0 or n ==1 : return 1; else: while(count < n +1): # count = 2 S = fn1 + fn2 fn1 = fn2 fn2 = S count = count + 1 return S

And there it is ! See ya !