From 100% to 0% CPU with memoization

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)]))

Enter fullscreen mode Exit fullscreen mode

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)]))

Enter fullscreen mode Exit fullscreen mode

Takes less than a second to run and almost no CPU resorces:

real    0m0.156s
user    0m0.075s
sys     0m0.059s

Enter fullscreen mode Exit fullscreen mode

原文链接：From 100% to 0% CPU with memoization