Description

Login

Syncing account progress…

Back

Advanced · 15 min

Recursion and caching

Solve self-similar problems and reuse calculated results.

Define a base case

A recursive function calls itself with a smaller problem. The base case stops the calls.

def factorial(number):
    if number <= 1:
        return 1
    return number * factorial(number - 1)

print(factorial(4))

Output

24

Cache repeated work

functools.cache stores results by argument. Later calls with the same value reuse the stored result.

from functools import cache

@cache
def ways(steps):
    if steps <= 1:
        return 1
    return ways(steps - 1) + ways(steps - 2)

print(ways(5))

Output

8

Recursion and caching

  1. Read both recursion and caching examples before answering.
  2. Run the task, compare its exact output, and revise the code if needed.

Try it yourself

Code runs on this device. When you are signed in, drafts sync to your account.

Sum nested numbers

Complete nested_sum so it recursively adds integers from nested lists. Display 10 for the supplied data.

Practice