Skip to content

DEV Community

Elijah Jeremiah L. Barba

Posted on Dec 16, 2019

Recursion in Python(A Gentle Introduction)

#python #resources #beginners

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:

ejbarba

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!

Top comments (1)

Subscribe

Jaako • Dec 16 '19 • Edited

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.

Read next

State-Space Models Adapt by Gradient Descent, Learning in Context

Mike Young - Oct 20

A beginner's guide to the Nsfw-Filter model by M1guelpf on Replicate

Mike Young - Oct 20

What I’ve Learned from Building a Calculator with Vue.js

William Kwadwo Owusu - Oct 19

Building RESTful APIs with Node.js and Express: Step-by-Step Tutorial

Ashish prajapati - Oct 19