_01a_fibo_rec Namespace Reference

Fibonacci sequence. More...

Functions
def	fiboDumb (n)
	This is a naive recursive version. More...
def	fibo (n, p=False)
	Generates a Fibonacci number using a recursive algorithm that makes only n recursive calls. More...
def	fib (n)
	Generates a Fibonacci number using a recursive algorithm that makes only n recursive calls. More...
def	fib2 (n, p0, p1)
	Generates a Fibonacci number using a recursive algorithm that makes only n recursive calls. More...
def	main ()

Detailed Description

Fibonacci sequence.

The Fibonacci Sequence is the series of numbers: \(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...\)
where the next number is found by adding up the two numbers before it.

Author

Paulo Roma

See also

http://en.wikipedia.org/wiki/Fibonacci_number

http://www.cs.northwestern.edu/academics/courses/110/html/fib_rec.html

http://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence

Function Documentation

fib()

def _01a_fibo_rec.fib

(

n

)

Generates a Fibonacci number using a recursive algorithm that makes only n recursive calls.

This function just calls fib2.

Parameters

n	index of a Fibonacci number.

Returns

the nth Fibonacci number.

See also

fib2

References fib2().

Referenced by main().

fib2()

def _01a_fibo_rec.fib2	(		n,
			p0,
			p1
	)

Generates a Fibonacci number using a recursive algorithm that makes only n recursive calls.

Parameters

n	index of a Fibonacci number.
p0	a Fibonacci number.
p1	the Fibonacci number following p0.

Returns

the nth Fibonacci number: p0+p1.

Referenced by fib().

fibo()

def _01a_fibo_rec.fibo	(		n,
			p = False
	)

Generates a Fibonacci number using a recursive algorithm that makes only n recursive calls.

Parameters

n	index of a Fibonacci number.
p	turns printing on or off.

Returns

the nth Fibonacci number.

Referenced by main().

fiboDumb()

def _01a_fibo_rec.fiboDumb

(

n

)

This is a naive recursive version.

The number of calls is \(O((\frac {(1+\sqrt{5})}{2})^n) = O(1.618^n)\), that is, for n = 20 there are 21891 calls.

Parameters

n	index of a Fibonacci number.

Returns

the nth Fibonacci number.

Referenced by main().

main()

def _01a_fibo_rec.main

(

)

References fib(), fibo(), fiboDumb(), and _01d_dec2bin.input.