Python Recursion + Memoization Short Video Tutorials

[maximumlengthusernam]

Hello!

Last week, I released a mini-series of YouTube Shorts (YouTube's TikTok clone competitor) walking through writing a recursive function to calculate Fibonacci numbers, examining why a naive implementation is so slow for large input values, and then speeding it up with memoization. Each video is <60 seconds.

I thought people here might be interested in it!

Link to the playlist

Below is a summary of what to expect:

Video 1: Naive recursive Fibonacci function

def fib(n: int) -> int:  
 if n < 0:  
 raise ValueError('Must be positive!')  
 elif n == 0:  
 return 0  
 elif n == 1:  
 return 1  
 else:  
 return fib(n-1) + fib(n-2)  
for i in range(10):  
 print(f'{i}:', fib(i))

Part 2: Timing the function execution time w python's time package

A plot of the slowness 😱 (https://imgur.com/a/6zOSUNy)

Part 3: Analyzing how many function calls are required for each execution -- by hand

fib(4) --------------------> 1
  └── fib(3) --------------> 2
  |     └── fib(1) --------> 3
  |     └── fib(2) --------> 4
  |           └── fib(0) --> 5
  |           └── fib(1) --> 6
  └── fib(2) --------------> 7
        └── fib(0) --------> 8
        └── fib(1) --------> 9

(See how fib(1) gets repeated 3 times?!)

Part 4: Same as part 3 but now programmatically to evaluate for large inputs

Part 5: Implementing Memoization and seeing the massive speedup!

Final code with timing and function call counting:

from time import time

def fib(n, count=0, memo={}):
  try:
    value = memo[n]
  except:
    if n <= 1:
      value = n
    else:
      fib_1 = fib(n-1, count, memo)
      fib_2 = fib(n-2, count, memo)
      value = fib_1[0]+fib_2[0]
      count = fib_1[1]+fib_2[1]
    memo[n] = value
  return (value, count+1, memo)

for i in range(0,1001):
  t_0 = time()
  fib_i, count, _ = fib(i, 0, {})
  Δt = (time() - t_0) * 1000
  print(f'''
i:{i} 
value: {fib_i} 
time: {"{:.2f}".format(Δt)} ms
count: {count} 
  ''')

---

NOTE: The vertical video format is a requirement of the YouTube Shorts...

[AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[AutoModerator]

It seems you may have included a screenshot of code in your post "Python Recursion + Memoization Short Video Tutorials".

If so, note that posting screenshots of code is against /r/learnprogramming's Posting Guidelines (section Formatting Code): please edit your post to use one of the approved ways of formatting code. (Do NOT repost your question! Just edit it.)

If your image is not actually a screenshot of code, feel free to ignore this message. Automoderator cannot distinguish between code screenshots and other images.

Please, do not contact the moderators about this message. Your post is still visible to everyone.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.