#!/usr/bin/env python
#
# recursion
#

def fibfast(num):
  fibarray=[1,1] 
  i = 2
  while(i <= num):
    fibarray.append(fibarray[i-2] + fibarray[i-1])
    i+=1
  return fibarray[num]

def fib(num):
  if num <= 1: 
    return 1
  else:
    return fib(num-1) + fib(num-2)
	
# T(n) = T(n-1) + T(n-2)  = 2T(n-2) + T(n-3) = 3T(n-3) + 2T(n-4) 
# = 5T(n-4) + 3T(n-5)
# At 30 the difference in speed is noticeable

# 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 
print(fibfast(30))