Recursion in Python(A Gentle Introduction)

The topic of recursion can be intimidating and daunting at first to newcomers, and one can get frustrated and find difficulties wrapping their heads around this topic. 🤔

MIT OpenCourseWare

Prof. Eric Grimson framed recursion in a straightforward and easy to understand way. He also introduced a simple yet powerful concept that goes with recursion called memoization. 🤯

One can think of memoization is essentially a list of performed tasks and its values, and if the task at hand is in the list, just get the value; else add the task and value to the list.😀

Notes:
Here is a great resource for Python beginners on recursion:

Recursion in Python(A Gentle Introduction)

Elijah Jeremiah L. Barba ・ Dec 16 '19

#python #resources #beginners

Jokes aside, after watching the video, you're at least a little confident with recursion👏👏👏 Happy Coding!

Comments

[Jaako]

Cool post-Elijah!, Memoization works great for recursion! Although it kinda sounds like Tweety bird pronouncing memorization the same way he pronounces "I thought I thaw a putty cat". Nevertheless here is how you can implement it in Python.

Instead of doing this which consumes a lot of memory:

def fibonacci(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n > 2:
        return fibonacci(n-1) + fibonacci(n-2)

You add memoization to optimize the recursion:

fibonacci_cache = {}

def fibonacci(n):
    # If we have cached the value, then return it
    if n in fibonacci_cache:
         return fibonacci_cache[n]

    # Compute the Nth term
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n > 2:
        return fibonacci(n-1) + fibonacci(n-2)

    # Cache the value and return it
    fibonacci_cache[n] = value
    return value

Or you can also use a builtin python tool:

from functools import lru_cache

@lru_cache(maxsize = 1000)
def fibonacci(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n > 2:
        return fibonacci(n-1) + fibonacci(n-2)

Here is the complete video explaining it clearly, plus it is where I got this code from.