#!/usr/bin/python
#Copyleft (C) 1996 William Totten
#biell@udel.edu

#This program implements the fibonnaci number generating alogithims.
#Recurrence relation:
#fib(0)=0
#fib(1)=1
#fib(n)=fib(n-1) + fib(n-2)

#Recursive implementation of the algorithm
def fib_r(n):
	if(n<=1):
		return n
	else:
		return fib_r(n-1) + fib_r(n-2)

#Iterative implementation of the algorightm
def fib_i(n):
	if(n<=1):
		return n
	else:
		last_last=0
		last=1
		while(n>1):
			now=last+last_last
			last_last=last
			last=now
			n=n-1
		return now

if __name__ == '__main__':
	from sys import argv
	from posix import times
	n=eval(argv[1])
	t=times()[0]
	print "Iterative: ", fib_i(n), ", User Time: ", times()[0] - t
	t=times()[0]
	print "Recursive: ", fib_r(n), ", User Time: ", times()[0] - t