SyntaxPilot
Courses/Python/Lesson 15

Python · Lesson 15 of 40 · 10 min

Recursion

queued

These are the notes for Python episode 15, the last episode of the basics section. Some problems have a shape that loops can't handle neatly: folders inside folders inside folders, as deep as they like. A loop needs to know the depth in advance, so we invent recursion: a function that calls itself on a smaller version of the same problem. You will learn why nested loops break on nested data, the cinema-queue trick, the base case and RecursionError, factorial traced call by call, the call stack, adding up folders of any depth, digit sums, why plain Fibonacci is so slow, memoization with a dictionary and @lru_cache, the recursion limit, and when a loop is the better tool. Every example below runs as-is in the SyntaxPilot compiler, with its real output from Python 3.13.

The problem: how big is this folder?

Your phone wants to know how big a folder is. If the folder only holds files, one loop adds up their sizes. But a folder can hold another folder. Let's model it: a folder is a list, a number is a file size (in KB), and a list inside the list is a sub-folder. For each item: if it's a list, loop through it too; otherwise add it.

folder = [10, 20, [5, 5]]

total = 0
for item in folder:
    if type(item) == list:
        for x in item:
            total += x
    else:
        total += item
print(total)

Output:

40

It works, for one level of sub-folder. Now put one more folder inside the sub-folder: 5, and a list of 3 and 2.

folder = [10, 20, [5, [3, 2]]]

total = 0
for item in folder:
    if type(item) == list:
        for x in item:
            total += x
    else:
        total += item
print(total)

Output:

Traceback (most recent call last):
  File "main.py", line 7, in <module>
    total += x
TypeError: unsupported operand type(s) for +=: 'int' and 'list'

Why: the inner loop expects only numbers, but it met the list [3, 2], and Python can't add a list to an int. Each nested loop handles exactly one level: two levels need two loops, ten levels need ten. Loops need to know the depth in advance, and real folders don't tell you how deep they go. We need code that handles any depth.

The cinema-queue trick

You're in a long cinema queue and want to know how many people are ahead of you, but you can't see the front.

Step What happens In recursion terms
1 The queue is too long to count yourself a big problem
2 You ask the person in front: "how many people are ahead of you?" They don't know either, so they ask the person in front of them the same question, one step smaller (the recursive case)
3 The question reaches the first person: "nobody, zero!" someone knows the answer directly (the base case)
4 Answers come back down the line: 0, 1, 2, ... each person adds one and passes it back each call returns its answer to the call that asked

Nobody counted the whole queue. Each person did one tiny step. Here is the queue in code (a sneak preview; the next sections explain every part):

def people_ahead(queue):
    if len(queue) == 0:
        return 0
    return 1 + people_ahead(queue[1:])

print(people_ahead(["Asha", "Ravi", "Meera", "Kabir"]))

Output:

4

A function that calls itself

In code, "asking the person in front" is a function calling itself. A countdown prints n, then calls countdown with n - 1:

def countdown(n):
    print(n)
    countdown(n - 1)

countdown(3)

Output (the full output is about a thousand lines; here are the first few and the last ones):

3
2
1
0
-1
-2
...
-994
-995
Traceback (most recent call last):
  File "main.py", line 5, in <module>
    countdown(3)
    ~~~~~~~~~^^^
  File "main.py", line 3, in countdown
    countdown(n - 1)
    ~~~~~~~~~^^^^^^^
  File "main.py", line 3, in countdown
    countdown(n - 1)
    ~~~~~~~~~^^^^^^^
  File "main.py", line 3, in countdown
    countdown(n - 1)
    ~~~~~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

In the video, to keep the screen short, the countdown only prints every 250th number:

def countdown(n):
    if n % 250 == 0:
        print(n)
    countdown(n - 1)

countdown(3)

Output:

0
-250
-500
-750
Traceback (most recent call last):
  File "main.py", line 6, in <module>
    countdown(3)
    ~~~~~~~~~^^^
  File "main.py", line 4, in countdown
    countdown(n - 1)
    ~~~~~~~~~^^^^^^^
  File "main.py", line 4, in countdown
    countdown(n - 1)
    ~~~~~~~~~^^^^^^^
  File "main.py", line 4, in countdown
    countdown(n - 1)
    ~~~~~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

It went straight past zero and never stopped. A function that calls itself is recursive, and the idea is recursion.

The missing base case: RecursionError

Why did it crash? Nobody in this queue ever says "zero, stop". Every call makes another call, forever: 0, -1, -2, ... Python allows about a thousand calls deep, then stops the program with RecursionError: maximum recursion depth exceeded. The line [Previous line repeated 996 more times] is Python shortening the traceback, which would otherwise be a thousand identical entries.

The fix is the base case: if n is 0, print "Lift off!" and return without calling again.

def countdown(n):
    if n == 0:
        print("Lift off!")
        return
    print(n)
    countdown(n - 1)

countdown(3)

Output:

3
2
1
Lift off!

The rule: base case + smaller call

Every recursive function needs two parts:

Part Job In countdown
Base case the simplest input, answered directly, with no more calls if n == 0: print "Lift off!" and return
Recursive case call the same function on a smaller problem countdown(n - 1)

The smaller call is what guarantees you reach the base case. If the input never gets smaller (or skips past the base case), you're back to RecursionError. You just invented recursion.

Factorial

Five factorial (written 5!) is 5 × 4 × 3 × 2 × 1 = 120. Notice: 5! is just 5 × 4!, the same problem one step smaller. And 1! is simply 1. That's the whole recursive function:

def fact(n):
    if n == 1:
        return 1
    return n * fact(n - 1)

print(fact(5))
print(fact(10))

Output:

120
3628800
  • Base case: if n == 1: return 1.
  • Recursive case: return n * fact(n - 1).
  • Note the return in front of the recursive call: the answer has to be passed back to whoever asked.

Watching factorial, call by call

How does Python remember all those waiting multiplications? Let's make every call announce itself: when it's called, and what it returns, indented by depth (" " * (5 - n) adds two spaces per level).

def fact(n):
    print("  " * (5 - n) + "fact(" + str(n) + ") called")
    if n == 1:
        return 1
    result = n * fact(n - 1)
    print("  " * (5 - n) + "fact(" + str(n) + ") returns", result)
    return result

fact(5)

Output:

fact(5) called
  fact(4) called
    fact(3) called
      fact(2) called
        fact(1) called
      fact(2) returns 2
    fact(3) returns 6
  fact(4) returns 24
fact(5) returns 120

fact(5) calls fact(4), which calls 3, 2, 1. Each call waits for the one below it. Then the answers come back up: 2, 6, 24, 120. Just like the cinema queue: the questions go down the line, the answers come back. (fact(1) prints no "returns" line because it hits the base case and returns before reaching that print.)

The call stack: a pile of plates

Python keeps the waiting calls in the call stack. Think of a pile of plates at a wedding buffet:

         +------------------------+
  top -> | fact(1)   returns 1    |   <- worked on now
         +------------------------+
         | fact(2)   waits: 2 * ? |
         +------------------------+
         | fact(3)   waits: 3 * ? |
         +------------------------+
  • Each call is a plate (a stack frame) put on top of the pile. It holds that call's own n and the line it's waiting on.
  • Only the top plate is worked on. When it returns, it's taken off.
  • fact(1) = 1 → then fact(2) can finish: 2 → then fact(3): 6.
  • If the pile gets about 1000 plates high, Python stops: RecursionError.

Each call has its own n (local scope, episode 14), which is why fact(3)'s n isn't overwritten by fact(2)'s.

Folder size at any depth

Back to the folder problem, now with recursion. The size of a folder: for each item, if it's a list, it's a folder, so ask size() of that folder (the same question, one step smaller). Otherwise add the file size.

def size(folder):
    total = 0
    for item in folder:
        if type(item) == list:
            total += size(item)
        else:
            total += item
    return total

print(size([10, 20, [5, 5]]))
print(size([10, 20, [5, [3, 2]]]))
print(size([1, [2, [3, [4, [5]]]]]))

Output:

40
40
15

Where's the base case? A folder that holds only files makes no more calls, so the recursion stops by itself. One level, two levels, five levels deep: any depth, with no extra loops. Recursion fits nested data (data that contains smaller pieces of the same shape).

Digit sum

One more small one: the sum of the digits of 2026. The last digit is n % 10, and the rest of the number is n // 10. Base case: a single digit (n < 10) is its own digit sum.

def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)

print(digit_sum(2026))

Output:

10

2 + 0 + 2 + 6 = 10. Each call strips one digit and passes the rest along: digit_sum(2026) = 6 + digit_sum(202) = 6 + 2 + digit_sum(20) = 6 + 2 + 0 + digit_sum(2) = 6 + 2 + 0 + 2.

Slow Fibonacci

The Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, ... Each one is the sum of the two before it, so fib(n) = fib(n - 1) + fib(n - 2), with fib(0) = 0 and fib(1) = 1 as the base cases. That's two recursive calls each time, and they ask many of the same questions again: fib(5) works out fib(3) twice and fib(2) three times.

Plain recursive Fibonacci, with a global counter (episode 14) for the number of calls, and a timer from the time module:

import time
calls = 0
def fib(n):
    global calls
    calls += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

start = time.time()
print(fib(35), "calls:", calls)
print("seconds:", round(time.time() - start, 1))

Output (the seconds depend on your machine; expect a few seconds):

9227465 calls: 29860703
seconds: 2.6

29,860,703 calls (almost 30 million) for one number. Each extra step roughly multiplies the work by 1.6, so fib(50) would take hours. The answers to small questions like fib(2) are worked out millions of times.

Memoization with a dictionary

The real-life fix is obvious: write each answer down the first time, and look it up after that. In programming this is called memoization. A dictionary memo (episode 12) maps n → fib(n). Before working anything out, check: is n in memo? Then return the saved answer. Otherwise work it out, save it, return it.

memo = {}
def fib(n):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

print(fib(35))
print(fib(100))

Output:

9227465
354224848179261915075

fib(35) instantly, and even fib(100), a 21-digit number. Each answer is worked out once. With the same call counter added, the memo version of fib(35) makes 69 calls instead of 29,860,703.

@lru_cache: Python remembers for you

Python can do the memoization for you. Import lru_cache from the functools module and write @lru_cache on the line above the function:

from functools import lru_cache

@lru_cache
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(100))

Output:

354224848179261915075

The same answer, and the function itself is the simple, slow-looking version. The cache (a store of saved answers) remembers for us. The @ line is called a decorator: it wraps a function to add behaviour. We'll build our own decorators in episode 25. (LRU stands for "least recently used", the rule for which answers to forget if the cache gets full; with plain @lru_cache it keeps up to 128 answers.)

The recursion limit

sys.getrecursionlimit() shows how deep Python lets you go. Then try fact(5000):

import sys
print(sys.getrecursionlimit())

def fact(n):
    if n == 1:
        return 1
    return n * fact(n - 1)

print(fact(5000))

Output:

1000
Traceback (most recent call last):
  File "main.py", line 9, in <module>
    print(fact(5000))
          ~~~~^^^^^^
  File "main.py", line 7, in fact
    return n * fact(n - 1)
               ~~~~^^^^^^^
  File "main.py", line 7, in fact
    return n * fact(n - 1)
               ~~~~^^^^^^^
  File "main.py", line 7, in fact
    return n * fact(n - 1)
               ~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

The limit is 1000, so 5000 calls deep is a RecursionError even with a correct base case. The limit protects your program from running out of memory for the call stack. For very deep problems, a loop is the safer tool:

def fact_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(fact_loop(5))
big = fact_loop(5000)
print(big > 10 ** 16000)

Output:

120
True

The loop has no depth limit: 5000! is a number with more than 16,000 digits, worked out without a single nested call.

Recursion vs loops

Recursion Loop
Best for nested data of unknown depth: folders, menus inside menus, family trees a known sequence: counting, going through a list, repeating n times
Code often shorter, mirrors the problem's definition (n! = n × (n-1)!) sometimes longer, but straightforward
Depth limited to about 1000 calls by default no limit
Speed and memory each call adds a stack frame; repeated work can explode (use memoization) usually faster, uses less memory
Danger forgetting the base case → RecursionError forgetting to update the counter → an infinite loop

Rule of thumb: if the data is nested (a thing contains smaller things of the same kind), reach for recursion. If it's a flat sequence or very deep, use a loop.

Common mistakes

Mistake What you see Why Fix
no base case: countdown(n - 1) always RecursionError: maximum recursion depth exceeded every call makes another call if n == 0: return
return n * fact(n) (same n) RecursionError: maximum recursion depth exceeded the problem never gets smaller fact(n - 1)
fact(0) when the base case is n == 1 RecursionError: maximum recursion depth exceeded 0, -1, -2 ... skip past the base case check n <= 1, or don't allow 0
forgetting return before the call: n * fact(n - 1) TypeError: unsupported operand type(s) for *: 'int' and 'NoneType' the function returns None, which can't be multiplied return n * fact(n - 1)
size(item) without adding the result no error, the wrong total (30 instead of 40) the sub-folder's answer is thrown away total += size(item)
nested loops for nested folders TypeError: unsupported operand type(s) for +=: 'int' and 'list' loops handle a fixed depth call size(item) recursively
plain fib(35) no error: 29,860,703 calls and a long wait the same answers recomputed a memo dict or @lru_cache
fact(5000) recursively RecursionError: maximum recursion depth exceeded deeper than the 1000 limit use a loop

Mini project: the size of a whole drive

A folder is a dictionary: a file name maps to its size in KB, and a folder name maps to another dictionary. folder_size() loops over items(). If an item is a dictionary, it's a folder, so call folder_size() on it. It works for the whole drive or any folder inside it, at any depth.

# Mini project: total size of a folder tree
drive = {
    "photos": {"trip.jpg": 300, "family.jpg": 250},
    "notes.txt": 4,
    "college": {"sem1": {"maths.pdf": 120}, "cv.pdf": 80},
}

def folder_size(folder):
    total = 0
    for name, item in folder.items():
        if type(item) == dict:
            total += folder_size(item)
        else:
            total += item
    return total

print("Drive:", folder_size(drive), "KB")
print("College:", folder_size(drive["college"]), "KB")

Output:

Drive: 754 KB
College: 200 KB

300 + 250 + 4 + 120 + 80 = 754. College alone is 120 + 80 = 200.

Extend it: also count the number of files (practice 3 below).

Practice

1. Write power(base, exp) with recursion (no **).

Solution
def power(base, exp):
    if exp == 0:
        return 1
    return base * power(base, exp - 1)

print(power(2, 10))
print(power(5, 3))
print(power(7, 0))

Output:

1024
125
1

Base case: anything to the power 0 is 1. Recursive case: base ** exp is base * base ** (exp - 1).

2. Reverse a string recursively.

Solution
def reverse(s):
    if len(s) <= 1:
        return s
    return reverse(s[1:]) + s[0]

print(reverse("python"))
print(reverse("a"))
print(reverse(""))

Output:

nohtyp
a

Reverse everything after the first letter, then put the first letter at the end. An empty or one-letter string is already reversed (the last line of output is the empty string).

3. Count all the files in the drive project.

Solution
drive = {
    "photos": {"trip.jpg": 300, "family.jpg": 250},
    "notes.txt": 4,
    "college": {"sem1": {"maths.pdf": 120}, "cv.pdf": 80},
}

def count_files(folder):
    count = 0
    for name, item in folder.items():
        if type(item) == dict:
            count += count_files(item)
        else:
            count += 1
    return count

print("Files:", count_files(drive))
print("College files:", count_files(drive["college"]))

Output:

Files: 5
College files: 2

The same shape as folder_size(): add 1 for a file instead of its size.

4. Add up a list recursively (no sum(), no loop).

Solution
def list_sum(nums):
    if len(nums) == 0:
        return 0
    return nums[0] + list_sum(nums[1:])

print(list_sum([4, 8, 15, 16, 23, 42]))
print(list_sum([]))

Output:

108
0

The sum of a list is its first item plus the sum of the rest; the sum of an empty list is 0.

5. Check whether a word is a palindrome (reads the same backwards), recursively.

Solution
def is_palindrome(word):
    if len(word) <= 1:
        return True
    if word[0] != word[-1]:
        return False
    return is_palindrome(word[1:-1])

print(is_palindrome("level"))
print(is_palindrome("racecar"))
print(is_palindrome("python"))
print(is_palindrome("abba"))

Output:

True
True
False
True

Two base cases: a word of 0 or 1 letters is a palindrome, and mismatched end letters mean it isn't. Otherwise check the middle, word[1:-1].

6. Print fib(1) to fib(50) fast.

Solution
memo = {}
def fib(n):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

for i in range(1, 51):
    print(fib(i), end=" ")
print()

Output:

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 

The memo dictionary is shared across the calls, so each new fib(i) reuses the answers already saved. Without it, this loop would take hours.

7. How deep is a folder? [10, 20] is 1 level, [10, 20, [5, [3, 2]]] is 3.

Solution
def deepest(folder):
    best = 0
    for item in folder:
        if type(item) == list:
            d = deepest(item)
            if d > best:
                best = d
    return best + 1

print(deepest([10, 20]))
print(deepest([10, 20, [5, [3, 2]]]))
print(deepest([1, [2, [3, [4, [5]]]]]))

Output:

1
3
5

A folder's depth is 1 plus the depth of its deepest sub-folder.

Quick quiz

1. The video's quiz:

def f(n):
    if n == 0:
        return 0
    return n + f(n - 1)

print(f(4))

What does it print? 4, 10, 24, or RecursionError?

Answer

10. f(4) = 4 + f(3) = 4 + 3 + f(2) = 4 + 3 + 2 + 1 + f(0) = 10. It adds instead of multiplies, so it's not 24, and the base case n == 0 is reached, so there's no error.

2. In what order are the numbers printed?

def show(n):
    if n == 0:
        return
    show(n - 1)
    print(n)

show(3)
Answer
1
2
3

The print comes after the recursive call, so each call waits until all the calls below it have finished. show(1) prints first, on the way back up.

3. What does this print?

def g(s):
    if s == "":
        return 0
    return 1 + g(s[1:])

print(g("chai"))
Answer

4. It counts the letters: each call adds 1 and passes the rest of the string along, like the cinema queue. It's a recursive len().

4. fact(n) has the base case if n == 1: return 1. What happens with fact(0)?

Answer

RecursionError: maximum recursion depth exceeded. 0, -1, -2 ... never equals 1, so the base case is skipped. Use if n <= 1: to be safe.

Interview questions

  1. What is recursion? A function that calls itself to solve a smaller version of the same problem, until it reaches a case it can answer directly.
  2. What are the two parts of a recursive function? A base case that returns without recursing, and a recursive case that calls the function on a smaller input that moves towards the base case.
  3. What causes RecursionError? Going deeper than Python's recursion limit (1000 by default): usually a missing or unreachable base case, or a correct function on a very deep input.
  4. What is the call stack? The stack of active function calls; each call gets a frame with its own local variables, pushed when called and popped when it returns.
  5. Why is naive recursive Fibonacci slow, and how do you fix it? It recomputes the same values exponentially many times (29,860,703 calls for fib(35)). Memoization (a dict or @lru_cache) stores each result so it's computed once, making it linear.
  6. When would you choose recursion over a loop? For naturally recursive or nested data (trees, folders, nested lists or dicts). For flat sequences or very deep inputs, a loop is faster and has no depth limit.
  7. Can every recursive function be written as a loop? Yes; sometimes you need your own list to act as the stack. Python doesn't optimise tail calls, so deep recursion is converted to loops in practice.

Glossary

Term Meaning Example
Recursion Solving a problem by having a function call itself on a smaller version of it fact(n) calls fact(n - 1)
Recursive function A function that calls itself countdown, fact, size
Recursive case The part that calls the function again with a smaller input return n * fact(n - 1)
Base case The simplest input, answered directly without another call; it stops the recursion if n == 1: return 1
Call stack The pile of calls waiting to finish; the newest is on top fact(3) → fact(2) → fact(1)
Stack frame One call on the stack, with its own local variables the "plate" for fact(2) with n = 2
RecursionError The error when calls go deeper than the recursion limit maximum recursion depth exceeded
Recursion limit The maximum call depth Python allows, 1000 by default sys.getrecursionlimit()
sys.getrecursionlimit() Returns the current recursion limit prints 1000
Factorial n! = n × (n-1) × ... × 1 fact(5) → 120
Fibonacci The sequence where each number is the sum of the two before 0, 1, 1, 2, 3, 5, 8
Digit sum The sum of a number's digits digit_sum(2026) → 10
Nested data Data that contains smaller pieces of the same shape [10, 20, [5, [3, 2]]]
Memoization Saving each answer the first time and reusing it memo[n] = ...
Cache A store of saved answers for quick reuse the memo dict
lru_cache A tool in functools that adds memoization to a function @lru_cache
Decorator An @name line above a function that wraps it with extra behaviour (episode 25) @lru_cache
global Lets a function change a variable defined outside it (episode 14) global calls
time.time() The current time in seconds; subtract two readings to time code time.time() - start
Palindrome A word that reads the same backwards "level"

Summary

  • Recursion is a function calling itself on a smaller version of the problem, like asking the person in front in a cinema queue.
  • Every recursive function needs a base case that stops, and a recursive case that calls itself with a smaller input.
  • No base case (or one that's never reached) → RecursionError: maximum recursion depth exceeded.
  • The call stack holds the waiting calls, like a pile of plates; Python's limit is about 1000 deep.
  • Recursion fits nested data of any depth: size() and folder_size() work however deep the folders go.
  • Repeated work makes recursion slow (29,860,703 calls for fib(35)); memoization with a memo dict or @lru_cache makes it instant.
  • For flat or very deep problems, use a loop.

Next episode: comprehensions, the start of the intermediate section. Building a whole list, dictionary or set in a single line, instead of four lines of loop.