CS1010E Chap.5 Recursion
Recursion
What recursion means in Python
Recursion solves a problem by expressing it through a smaller instance of the same problem. A function written this way calls itself, or more precisely a fresh copy of itself, with an argument that has shrunk in some measurable way: a number reduced by one, a string with a character removed, a tuple with its first item dropped.
The shrinking cannot continue forever, so every recursive definition also names a smallest problem whose answer needs no further work. Factorial is the classic illustration, since 0! is defined as 1 and every larger factorial is n multiplied by the factorial just below it.
Turning a recurrence relation into Python is mostly mechanical.
The base case becomes a branch that returns a value directly, the recursive case becomes a branch that returns an expression containing the smaller call, and an if statement decides which branch runs. Fibonacci translates just as directly, with two base values, 0 and 1, because each term depends on the two terms before it.
Winding, unwinding and the stack
Evaluating a recursive call happens in two phases.
During winding, calls keep opening on smaller and smaller arguments until one of them reaches the base case. During unwinding, the pending calls finish in reverse order, each one using the value returned from below to complete its own expression.
Python keeps track of the unfinished calls on the function activation stack, giving each call its own frame with its own parameter values, so a parameter named n can hold 3 in one frame and 1 in another at the same moment.
Elegant code is not always efficient code.
Plain recursive Fibonacci recomputes small terms many times over because it stores nothing between calls, and an iterative version that carries two running values does far less work.
Beyond formulas
Recursion also handles enumeration problems with no neat formula, such as listing every way to fill a row of parking lots with one-lot cars and two-lot buses, or moving a tower of discs between three poles under the Towers of Hanoi rules.
In Hanoi, moving n discs reduces to moving n minus 1 discs onto the spare pole, moving the largest disc once, and then moving the n minus 1 discs back on top of it, so a three-disc tower takes seven moves. The design habit that makes these tractable is one-layer thinking: settle the base case, check the next smallest size by hand, then write one layer that trusts the smaller call.
The Week 6 tutorial practises this on pricing strings, counting north-east paths on a grid, digit sums written both recursively and with loops, and fast exponentiation by divide and conquer, while Assignment 3 asks for recursive enumeration without loop constructs.
What this chapter covers
- 01
Recursive problems defined by smaller problems of the same kind
- 02
Base case and recursive case in a Python function
- 03
Translating factorial and Fibonacci recurrences into code
- 04
Winding and unwinding phases of a recursive call
- 05
Function activation stack and call frames
- 06
Recursive call trees and repeated subproblems
- 07
Recursion compared with iteration
- 08
One-layer thinking for enumeration and Towers of Hanoi
Worked example · free
Counting a character with a recursive function
fib(4) with each return value. The two orange boxes are the same subproblem solved twice, because nothing is stored between calls.- 1Choose the base case: an empty string contains no characters, so count_char('', c) returns 0.
- 2Write the recursive case: compare s[0] with c to get 1 or 0, then add count_char(s[1:], c), which works on a string one character shorter.
- 1Check termination: the length of s falls by exactly 1 per call, so the empty string is always reached.
- 2Trace the calls down to the base case and add the contributions back up to reach the result.
Key terms
- Recursive Function
- A function that solves its task by calling itself on a smaller argument, combining the returned value with a little work of its own.
- Base Case
- The branch that returns an answer directly without another recursive call; it is what stops the recursion.
- Recursive Case
- The branch that calls the function again on a smaller input so that the base case is eventually reached.
- Recurrence Relation
- A definition that expresses each value of a sequence or function in terms of smaller values, plus one or more starting values.
- Winding Phase
- Describes the stage where calls keep opening on smaller arguments until a base case is met.
- Unwinding Phase
- Describes the stage where pending calls finish in reverse order, each completing its expression with the value returned from below.
- Activation Stack
- Holds one frame per active function call, storing that call's parameters and local values until it returns.
- One-Layer Thinking
- Means designing a recursive function by getting one level correct and trusting that the smaller call already works.
Recursion FAQ
What happens if a recursive function has no reachable base case?
Python keeps opening new frames until it hits its recursion depth limit, then stops the program with a RecursionError. The usual causes are a missing base case, an argument that does not shrink, or an argument that jumps over the value the base case tests for, such as decreasing by 2 while checking only for 0.
Is recursion faster than a loop in Python?
Usually not. Each call costs a new stack frame, and naive recursive Fibonacci repeats the same subproblems many times, so fib(30) makes well over a million calls. Recursion earns its place through clarity, especially for enumeration and divide-and-conquer problems, and a loop version is often the better choice for simple counting or summing.
How many base cases does a recursive function need?
As many as the recursive case can land on without going further. A definition that looks back one step, like factorial, needs one; a definition that looks back two steps, like Fibonacci or filling lots with one-lot and two-lot vehicles, needs two, otherwise a call can skip past the single stopping value.
Why does my recursive function return None?
The recursive line was probably evaluated without being returned. Python discards the value of an expression statement, so the function falls off its end and returns None, and the caller one level up then fails when it tries to add or concatenate that None. Put return in front of every branch that should produce a value.
Can tutorial-style problems be solved without loops at all?
Yes. Problems such as summing digits with integer division and remainder, counting grid paths, or raising a number to a power can all be written purely with recursion. Divide and conquer for powers cuts the number of multiplications sharply by halving the exponent at each step instead of reducing it by one.
Exam move
For every recursive function you write, first test the base case alone, then the next smallest input, before trying anything large. Then draw the call tree or stack frames for one small input by hand and compare your predicted return values with what Python prints.
Working through Recursion in CS1010E? Sia is AskSia’s AI Computer Science tutor — ask any CS1010E Recursion question and get a clear, step-by-step explanation grounded in how CS1010E is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
