Recursion and What’s Next

A recursive function is one that calls itself, working toward a base case that stops the recursion — you already saw this in the previous lesson’s merge_sort, which calls itself on smaller and smaller halves of the list.

A classic first example: factorial

def factorial(n):n    if n <= 1:          # base case -- stops the recursionn        return 1n    return n * factorial(n - 1)   # recursive casennprint(factorial(5))   # 5 * 4 * 3 * 2 * 1 = 120

Every recursive function needs exactly two things: a base case that stops it, and a recursive case that moves it closer to that base case. Forgetting the base case causes infinite recursion, which eventually crashes the program with a stack overflow error — the practical, real-world reason this is called a “stack” overflow, tying directly back to the stack data structure covered earlier in this course.

Recursion vs iteration

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

Anything recursion can do, a loop can also do, and often more efficiently, since recursion carries the overhead of a function call for every step. Recursion tends to be reached for specifically when a problem is naturally defined in terms of smaller versions of itself — tree traversal, and the divide-and-conquer sorting from the previous lesson, are both excellent fits.

A visual mental model

Picture each recursive call as adding a new layer to a stack of plates, and each return as removing the top plate — this maps directly onto the actual call stack the language runtime uses internally, and is genuinely the most useful way to reason about a recursive function’s behavior when you get stuck.

You have completed the course

You now understand Big O notation, core data structures, searching and sorting algorithms, and recursion — the shared toolkit underlying every language covered on this site. Take the certification assessment next to prove it.