I have followed the 30 first minutes of the freecodecamp training named Dynamic Programing for Beginners – How to Solve Coding Challenges with Memoization and Tabulation.
The first part is about programming efficiency and timing but also about infrastructure resources.
The training shows Javascript examples, but I moved to Python ♥️
The code:
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
print('The first 50 fibonacci numbers are:')
print(','.join([str(fib(n)) for n in range(50)]))
It takes too many CPU resources and it doesn't even finish:
Moving to:
def fib(n, memo={}):
if n in memo:
return memo[n]
if n == 0:
return 0
if (n <= 2):
return 1
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
print('The first 50 fibonacci numbers are:')
print(','.join([str(fib(n)) for n in range(50)]))
Takes less than a second to run and almost no CPU resorces:
real 0m0.156s
user 0m0.075s
sys 0m0.059s
Latest comments (3)
Great post,
Are you going to expand more on why this is the case?
Btw, going around your implementation, it can be reduced to something like:
Both have very similar performances.
Cheers,
Thank you!! The referred training from Freecodecamp goes deeper on the why and I think is quite cool to follow it. Is it what you mean?
Yeh. I was reading now the original post. I am definitively not an expert in dynamic programming, but definitively I use some those concepts in my daily programming even without knowing it.
Btw, is Fibonacci a good example to teach recursion, anyway?