"""The Fibonacci sequence is calculated using three
different programming styles:
     1. procedural
     2. functional
     3. recursive
The functional version uses faked lazy evaluation technique"""

def fib1(n):
	"""Procedural version, returns list"""
	i,a,b = 0,0,1
	list = []
	while i< n:
		list.append(b)
		i,a,b = i+1,b,a+b
	return list

def fib2(n):
	"""Functional version, returns list"""
	if n < 1:
		return []
	elif n == 1:
		return [1]
	l = [1,1]
	#list = [1,1] + [oneStep(l) for x in range(1,n-1)]
	list = [1,1] + map(lambda a: oneStep(l), range(1,n-1))
	return list

def oneStep(l):
	"""Takes a two element list [a,b] and returns the second
	element from the two element list [b,a+b]"""
	if len(l) == 2:
		a = l.pop(0)
		b = l.pop(0)
		l.append(b)
		l.append(a+b)
	return l[1]

def fib3(n):
	"""Recursive version, returns list"""
	if n < 1:
		return []
	elif n == 1:
		return [1]
	elif n == 2:
		return [1,1]
	else:
		list = fib3(n-1)[:]
		list.append(list[n-2] + list[n-3])
		return list
		
#to run the module 
if __name__ == "__main__":
	n = input("enter a number >= 0: ")
	print "The procedural non-recursive version returns: "
	print fib1(n)
	print "The functional version returns: "
	print fib2(n)
	print "The recursive version returns: "
	print fib3(n)