关于一个递归的改写问题
value = 1000
def fact(n) :
if n == 1 : return 1
else : return n * fact(n-1)
def callFib(n) : # a helper function to call the recursive function
store = [ ]
for i in range(n+1) :
store.append(None) # default initialising the list
store[0] = 0
store[1] = 1
store[2] = 1 # giving the initial correct values
if n <= 501 : # if the calculation won't make too many recursive calls
return fib(n, store)
else : # if the calculation will make too many recursive calls
return fibb(n, store)
def fib(n, my_store) : # the recursive efficient function
if my_store[n] == None : # if the value hasn't been calculate already
my_store[n] = fib(n-1, my_store) + fib(n-2, my_store)
return my_store[n]
def fibb(n, my_store) :
if n <= 1000 : # if the number of recursive calls is big but not horrendous
fib(501, my_store) # need to compute the next initial values
my_next_store = []
for i in range(n-500+1) :
my_next_store.append(None)
my_next_store[0] = my_store[500] # initialise a fresh list of values
my_next_store[1] = my_store[501]
fib(n-500, my_next_store) # re-use the recursive fn to compute the next batch
return my_next_store[n-500]
print( "The " +str(value)+ "-th fibonacci number = \n\t" +str( callFib(value) ) )
import time
def Fibonacci(n) :
fibCurrent = 1
fibNext = 1
for i in range(n//2) :
fibCurrent = fibCurrent + fibNext
fibNext = fibNext + fibCurrent
if n%2 :
return fibNext
else:
return fibCurrent
startTime = time.clock()
print(Fibonacci(10000))
endTime = time.clock()
print(endTime - startTime)
def fb(n):
if n < 1:
raise TypeError("n is not less than 1")
if n == 1:
return 0
elif n == 2:
return 1
else:
return fb(n-1)+fb(n-2)
print(fb(90))
