risehack_fibonacci.py

# Python 2.7.10 program
# Author = Rakshak R.Hegde

# Using recursion along with memoization
# to make an efficient solution  to print the first 'n' fib sequence

# Recursive relation required => f(n) = f(n-1) + f(n-2) where f(x) is the x'th fibonacci number
# Base values f(1) = f(2) = 1

# Advantages:
# - Highly portable code, just have to copy a class
# - Printing result as a last step, so that the list returned can be used in other programs for compatibility and reusability
# - Global variable _memo makes for faster results even for multiple calls

# How to use? => Call 'Fibonacci()[<required number>]'

class Fibonacci:
	_memo = {1: 1, 2: 1} # Regarded as private member, not to be accessed outside this scope

	def __getitem__(self, n):
		if n<=0:
			raise ValueError('Invalid input! Enter a number greater than 0')
		self.fib(n)
		result=[]
		for i in range(1, n+1):
			result.append(self._memo[i])
		return result

	# Recursive implementation
	def fib(self, n):
		if n not in self._memo:
			self._memo[n] = self.fib(n-1) + self.fib(n-2)
		return self._memo[n]

F = Fibonacci()
print F[1]
print F[2]
print F[5]
# print F[500]
# print F[1000]