#This is a function to calculate the nth fibonacci no.
#The idea here is to verify the concept of memoisation

##Trivial method where we don't store the already calculated
##values of Fib and thus we end up calling the same function
##a lot more times.
def Fib(n):
 global numCalls
 numCalls += 1
# print("fib called with " + str(n) )
 if n <= 1:
  return 1
 else:
  return Fib(n-1) + Fib(n-2)
numCalls = 0
n = int(input("Enter an integer "))
res = Fib(n)
print("Fib slow f " + str(n) + ", num calls " + str(numCalls))

def fastFib(n,memo):
 global numCalls
 numCalls += 1
 print("fib called with " + str(n) )
# print("not (n in memo) " + str(not (n in memo)) )
# for x in memo:
#  print(str(x))
# for x in range(5):
#  print( str(x) + " is not " + str(x in memo))
 if not (n in memo):
# memo[n] = fastFib(n-1,memo) + fastFib(n-2,memo)
  memo[n] = fastFib(n-2,memo) + fastFib(n-1,memo)
# print (str(memo))
 return memo[n]

def Fib1(n):
 memo = { 0:1, 1:1 }
 return fastFib(n,memo)

numCalls = 0
#n = 4
res = Fib1(n)
print("Fib1 of " + str(n) + ", num calls " + str(numCalls))


#NB# bool(#) = true is #!=0 and # is integer, bool(0)=False. 


#Check Recursion Tree to understand how a recursive fn in called.
# chck video https://www.youtube.com/watch?v=dxyYP3BSdcQ titled "Fibonacci Sequence - Anatomy of recursion and space complexity analysis"
#When a function is called, the calc. of the calling code is paused
#and a new space is allocated in memory to perform the calc for the 
#function. These are impelmented as stacks. For the case of recursion,
#when F(n) is called in the "main" it pauses the "main" code at that point
#and goes to "Fib1", defines memo and then calles "fastFib" (=F say). For what
#follows let n=6. F(6) is supposed to return F(5)+F(4) as 6 is not in "memo",
#since F(5) is encountered first it creastes a new spot on the top of the stack
#The flow of control is as follows
#F(5)->F(4)->F(3)->F(2)->F(1)
#Since F(1) is present in memo, we reurn 1, thus F(2) next calls F(0) which is also
#present in memo thus returns 1. Thus we have a value F(2) in memo. next level up
#F(3) now has F(2) so it calls F(1) (already stored in memo). Thus it can calculate it.
#F(4) now has F(3) so it calls F(2) (already stored in memo). Thus it can calculate it.
#F(5) now has F(4) so it calls F(3) (already stored in memo). Thus it can calculate it.
#This sort of explains why the sequence of calls is as made by the function is
# from n to 0 and then form 1 to n-2.
