Teaching Kids Programming – Computing Fibonacci Numbers using 3 Methods


Teaching Kids Programming: Videos on Data Structures and Algorithms

Mathematically, the Fibonacci Numbers are:

tex_c06a2e3d66c2fa10f871c18bf889edc1 Teaching Kids Programming - Computing Fibonacci Numbers using 3 Methods algorithms dynamic programming python recursive teaching kids programming youtube video
tex_c4ec2575b1c9bae6f84cbbf914ebaef8 Teaching Kids Programming - Computing Fibonacci Numbers using 3 Methods algorithms dynamic programming python recursive teaching kids programming youtube video
tex_6fccf014fbbe09a10050ee343d28e5ae Teaching Kids Programming - Computing Fibonacci Numbers using 3 Methods algorithms dynamic programming python recursive teaching kids programming youtube video

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 words
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

The Permanent URL is: Teaching Kids Programming – Computing Fibonacci Numbers using 3 Methods

Leave a Reply