DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets Manager

Snippets has posted 5883 posts at DZone. View Full User Profile

Fibonnacci

06.22.2009

| 688 views |

        // calculates the nth fibonacci number

def fibonacci(number):
	if number == 0 or number == 1:
		return number;
  	else:
		result = fibonacci(number-1) + fibonacci(number-2)
		return result

Tags:

fibonacci
Python

Comments

Snippets Manager replied on Wed, 2009/12/30 - 9:06pm

Well, you still can use recursion if you want, if you use memoisation. Just add each value to a dictionary, and take them from there on subsequent function calls, instead of recalculating.

Snippets Manager replied on Sat, 2009/07/04 - 11:28am

Calculates it inefficiently, though. Try fibonacci(40) for example. Takes a while? And burns CPU cycles? This is possible in a fraction of a second (so is the thousandth or ten-thousandth etc) as long as you don't use recursion. Recursion is great in many cases, but not here. To calculate the nth term, you call the function twice, one for n-1 and one for n-2. Each of those will also make two calls and so on. So adding one to n doubles the number of function calls! I won't plug my book or my course, but this is exactly one of the basic exercises. J