After this lesson, you will be able to: Write correct recursive functions by identifying the base case and recursive case, understand the call stack during recursion, and know when iteration is the better choice.
Recursion is a function calling itself to solve smaller versions of the same problem. It is the mental model behind merge sort, tree traversal, backtracking, and dynamic programming, so getting comfortable with it now pays off across the rest of the sub-track.
Every correct recursive function has two parts. The base case is the smallest input you can answer directly, with no further recursion; it stops the process. The recursive case breaks the problem into a smaller version and calls itself. If you forget the base case, the function recurses forever and overflows the stack. The skill is spotting how to express a problem in terms of a smaller version of itself.
Factorial and sum, the simplest examples.
def factorial(n):if n <= 1: # base casereturn 1return n * factorial(n - 1) # recursive case: smaller problem# Trace factorial(3):# factorial(3) = 3 * factorial(2)# factorial(2) = 2 * factorial(1)# factorial(1) = 1 <- base case, unwinds# = 3 * 2 * 1 = 6def list_sum(nums):if not nums: # base case: empty listreturn 0return nums[0] + list_sum(nums[1:])
Each recursive call pushes a new frame onto the call stack, holding that call's local variables and its place in the code. The frames stack up until a base case is hit, then they pop and unwind as each call returns. This is why deep recursion can overflow the stack (Python defaults to about 1000 frames). It is also why the stack lesson in the Data Structures sub-track is the foundation for understanding recursion: recursion is just the call stack doing the bookkeeping for you.
Practice spotting the base case and the smaller subproblem.
1. Reverse a string recursively: base case is the empty string; recursive case is last char + reverse(rest).
2. Compute the nth Fibonacci naively: base cases fib(0)=0, fib(1)=1; recursive case fib(n)=fib(n-1)+fib(n-2). Notice it is exponentially slow (this motivates the next lesson).
3. Sum a nested list (lists inside lists): base case is a number; recursive case recurses into each sublist.
4. For each, name the base case out loud before writing code.
Forgetting or mis-writing the base case, causing infinite recursion and a stack overflow. Not making progress toward the base case (the recursive call must shrink the problem). Recomputing the same subproblem exponentially (naive Fibonacci), which the next lesson fixes with memoization. Using recursion on inputs deep enough to overflow the stack when a loop would be safe. Building huge intermediate copies (nums[1:] copies the list each call, making it O(n squared)); pass indices instead.
Sign in and purchase access to unlock this lesson.