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
returnin 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
nand the line it's waiting on. - Only the top plate is worked on. When it returns, it's taken off.
fact(1)= 1 → thenfact(2)can finish: 2 → thenfact(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
- 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.
- 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.
- 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. - 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.
- 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. - 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.
- 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()andfolder_size()work however deep the folders go. - Repeated work makes recursion slow (29,860,703 calls for
fib(35)); memoization with amemodict or@lru_cachemakes 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.