Lesson 17 · 17 of 20

Recursion and memoization · Python

Recursive Python functions to walk a folder tree, and memoization with a dictionary to count the ways to pay an amount.

Python · Recursion and memoization in DMarlon Studio: the example's code and its output in the terminal

A recursive function calls itself on a smaller problem. Every recursion needs a base case that is solved without calling itself again. In size(item), if the item is not a dictionary it is a file and its size is returned; if it is a folder, it adds up size() for everything inside, and each of those calls goes one level deeper.

show(folder, depth=0) is recursive too: it prints each name indented by two spaces per level and, when it finds a folder, calls itself with depth + 1. Recursion fits data shaped like a tree (folders, menus, org charts, JSON), where you do not know in advance how many levels there are.

ways_to_pay(amount, coins) counts how many ways an amount can be paid with a set of coins. At each step there are two paths: use one coins[0] coin (leaving less to pay) or drop that coin for good (coins[1:]). The base cases are an amount of zero (one way, it is paid) and a negative amount or no coins left (no way).

On its own, that function would repeat the same subproblems millions of times. Memoization stores each answer in memo under the key (amount, coins) and reuses it when it comes up again. With only 238 stored cases it finds the 4562 ways to pay 1 euro. It is exactly what @lru_cache does for you.

Python limits recursion depth (about 1000 nested calls). For very deep structures, a loop with your own stack is safer.

Code · main.py

project = {                               # folders are dicts, files are KB    "README.md": 4,    "src": {"main.py": 12, "utils": {"dates.py": 3, "money.py": 5}},    "docs": {"manual.pdf": 820, "img": {"logo.png": 64}},}def size(item):    if not isinstance(item, dict):        # base case: a plain file        return item    return sum(size(child) for child in item.values())   # calls itselfdef show(folder, depth=0):    for name, item in folder.items():        print("  " * depth + f"{name} ({size(item)} KB)")        if isinstance(item, dict):            show(item, depth + 1)         # one level deepermemo = {}def ways_to_pay(amount, coins):           # amount in cents    if amount == 0:        return 1    if amount < 0 or not coins:        return 0    key = (amount, coins)    if key not in memo:                   # work out each case only once        use_it = ways_to_pay(amount - coins[0], coins)   # pay one coins[0]        skip_it = ways_to_pay(amount, coins[1:])         # never use it        memo[key] = use_it + skip_it    return memo[key]show(project)print("Ways to pay 1 EUR:", ways_to_pay(100, (50, 20, 10, 5, 2, 1)))print("Cases remembered:", len(memo))

Output · python3 main.py

README.md (4 KB)
src (20 KB)
  main.py (12 KB)
  utils (8 KB)
    dates.py (3 KB)
    money.py (5 KB)
docs (884 KB)
  manual.pdf (820 KB)
  img (64 KB)
    logo.png (64 KB)
Ways to pay 1 EUR: 4562
Cases remembered: 238

Key points

A recursive function calls itself on a smaller case.
Without a base case, recursion never ends.
It is a natural fit for trees: folders, menus, nested JSON.
Memoization stores results so they are not computed twice.
Python stops recursion at around 1000 nested calls.

Exercise

Write a recursive count_files(folder) that returns how many files there are in project (it should give 6).