Teaching Kids Programming: Videos on Data Structures and Algorithms
Mathematically, the Fibonacci Numbers are:
Fibonacci Number – Recursion
1 2 3 4 5 6 | def f(n): if n == 0: return 0 if n == 1 return 1 return f(n - 1) + f(n - 2) |
def f(n): if n == 0: return 0 if n == 1 return 1 return f(n - 1) + f(n - 2)
Fibonacci Number – Iterative
1 2 3 4 5 | def f(n): a, b = 0, 1 for i in range(n): a, b = b, a + b return a |
def f(n): a, b = 0, 1 for i in range(n): a, b = b, a + b return a
Fibonacci Number – Recursion with “NoteBook”
aka. Memoization, aka Dynamic Programming:
1 2 3 4 5 6 7 8 9 10 11 12 | def f(n, nb = {}): # first look it up in notebook if n in nb: return nb[n] if n == 0: return 0 if n == 1 return 1 ans = f(n - 1, nb) + f(n - 2, nb) # save the result in notebook nb[n] = ans return ans |
def f(n, nb = {}): # first look it up in notebook if n in nb: return nb[n] if n == 0: return 0 if n == 1 return 1 ans = f(n - 1, nb) + f(n - 2, nb) # save the result in notebook nb[n] = ans return ans
The {} dictionary object is used as a notebook i.e. cache/meomization. The intermediate Fibonacci numbers are computed and stored as key-value pairs in the “notebook”.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
358 wordsloading...
Last Post: Two Pointer Sliding Window to Compute the Longest Substring with At Most Two Distinct Characters
Next Post: Teaching Kids Programming - Reversing a List using Stack