Recursion Basics

Build the mental model

Recursion solves a problem by breaking it into a smaller version of the exact same problem, and calling the function itself to solve that smaller piece. Every correct recursive function needs two parts: a base case, the smallest input the function can answer directly without recursing further, and a recursive case, where it calls itself on a smaller input and combines that result with the current step's work. Consider factorial(n): the base case is factorial(0) = 1, answered immediately with no further call; the recursive case is factorial(n) = n * factorial(n - 1) for n > 0. Calling factorial(3) doesn't compute an answer right away — it calls factorial(2), which calls factorial(1), which calls factorial(0), each new call pausing its caller and pushing a fresh frame onto the call stack. Once factorial(0) returns 1, that answer flows back up: factorial(1) returns 1*1=1, factorial(2) returns 2*1=2, factorial(3) returns 3*2=6 — the stack unwinding in the exact reverse order it built up. If the base case is missing, wrong, or never reached (e.g. counting the wrong direction), calls keep pushing new frames forever, exhausting the call stack and crashing with a stack overflow.

Connect it to a real scenario

The Tutorial Platform's course content is naturally nested — a course contains chapters, each chapter contains lessons — which is exactly the shape recursion is built for. A function that renders a table of contents, or one that walks a lesson's prerequisite chain to check 'has the learner completed everything required before this lesson', can process a chapter or a prerequisite the same way it processes the whole course: solve the smallest case (a single lesson with no prerequisites) directly, and delegate everything larger to a recursive call on its sub-parts. Getting the base case right here is what stops that prerequisite check from looping forever if two lessons ever end up referencing each other.

• Every recursive function needs a base case (stops recursing) and a recursive case (calls itself on a smaller input)
• Each recursive call pushes a new frame onto the call stack; results flow back up as calls return, unwinding in reverse order
• A missing, wrong, or unreachable base case causes infinite recursion and crashes with a stack overflow

Try the working example

def factorial(n):
    # Base case: smallest input, answered directly, no further recursion
    if n == 0:
        return 1
    # Recursive case: solve a smaller subproblem, then combine with current step
    return n * factorial(n - 1)

# Trace for factorial(3):
#   factorial(3) -> 3 * factorial(2)
#     factorial(2) -> 2 * factorial(1)
#       factorial(1) -> 1 * factorial(0)
#         factorial(0) -> 1                (base case reached, stack starts unwinding)
#       factorial(1) returns 1 * 1 = 1
#     factorial(2) returns 2 * 1 = 2
#   factorial(3) returns 3 * 2 = 6
print('factorial(3) =', factorial(3))

Prints 'factorial(3) = 6', matching the traced call stack in the comments: four nested calls build up to factorial(0), then results unwind back up (1, 1, 2, 6).

Wikipedia — Recursion (computer science) — Data Structures & Algorithms