15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Recursion in data structure code is a function that solves a problem by calling itself on a smaller input. Each call keeps its own stack frame and waits for the smaller call to return, and a base case stops the chain. For sumTo(n), that means n + 1 calls: O(n) time and O(n) call-stack space.
| Contract first | Valid inputs, return value, behavior outside the domain, and whether it mutates input |
|---|---|
| Two parts | A base case that returns directly, and a recursive case that makes a smaller valid call |
| Time for sumTo(n) | O(n), one call per value from n down to 0 |
| Auxiliary space | O(n), n + 1 active frames at the deepest point |
| Termination | Each call must shrink the size measure and keep it valid |
A recursive function is a function that invokes itself.
Before writing one, state its contract:
For this lesson:
sumTo(n)accepts a nonnegative integernand returns the sum of all integers from1throughn. It does not mutate any input.
Examples from the contract:
sumTo(0) returns 0.sumTo(1) returns 1.sumTo(3) returns 6.sumTo(-1) is outside the contract. The chosen API policy should reject it or handle it explicitly.The recursive definition is:
The definition has two parts:
sumTo(n - 1).n.The size measure is n. Each recursive call must make that value smaller while keeping it valid.
Start with:
1sumTo(3)The contract says this must return:
Split the original problem into a smaller request:
1sumTo(3) = 3 + sumTo(2)The call sumTo(3) cannot finish yet. It must wait for sumTo(2) to return. Its pending work is:
13 + ...Then the smaller call makes another smaller request:
1sumTo(2) = 2 + sumTo(1)Its pending work is:
12 + ...Then:
1sumTo(1) = 1 + sumTo(0)Its pending work is:
11 + ...Now the call reaches sumTo(0). There are no integers from 1 through 0, so the sum is 0. The base case returns 0.
A call stack holds one frame for each active function call. Each frame stores its own parameter value and any work that must wait for a recursive result.
sumTo(3) pushes frames for 3, 2, 1 and 0 while each caller keeps its addition pending; once sumTo(0) returns 0, the frames pop and the totals 1, 3, 6 come back up.
Trace sumTo(3) one frame at a time.
| Step | Active call | Action | Pending work or returned value |
|---|---|---|---|
| 1 | sumTo(3) | Calls sumTo(2) | 3 + ... |
| 2 | sumTo(2) | Calls sumTo(1) | 2 + ... |
| 3 | sumTo(1) | Calls sumTo(0) | 1 + ... |
| 4 | sumTo(0) | Base case returns | 0 |
| 5 | sumTo(1) | Receives 0; computes 1 + 0 | returns 1 |
| 6 | sumTo(2) | Receives 1; computes 2 + 1 | returns 3 |
| 7 | sumTo(3) | Receives 3; computes 3 + 3 | returns 6 |
The calls move downward:
1sumTo(3)
2 calls sumTo(2)
3 calls sumTo(1)
4 calls sumTo(0)The return values move upward:
1sumTo(0) returns 0
2sumTo(1) returns 1
3sumTo(2) returns 3
4sumTo(3) returns 6Each non-base call requests a smaller range. sumTo(k) requests the range from 1 through k - 1.
While calls are active, each call has one clear responsibility:
For every active call
sumTo(k), that call is responsible for returning the sum of integers from1throughk. Its recursive request is only for the smaller range1throughk - 1.
This is the recursion invariant.
Look at the active frames for sumTo(3):
1sumTo(3) is responsible for 1 + 2 + 3.
2sumTo(2) is responsible for 1 + 2.
3sumTo(1) is responsible for 1.
4sumTo(0) is responsible for the empty sum.Each call keeps its own responsibility. A caller does not lose its value of n when it makes a recursive call. For example, sumTo(2) still knows it must add 2 after sumTo(1) returns.
The base case makes the invariant complete:
1sumTo(0) returns 0.That is exactly the sum of the empty range from 1 through 0.
Start from the contract:
1Input: a nonnegative integer n
2Output: the sum 1 + 2 + ... + n
3Mutation: noneNow separate the two possible cases.
n is zeroThere are no positive integers to add.
1sumTo(0) = 0The base case stops recursion.
n is greater than zeroThe answer contains n plus the sum of everything before it:
1sumTo(n) = n + sumTo(n - 1)The recursive input n - 1 is valid because if n > 0, then n - 1 >= 0.
It is also strictly smaller than n. Repeated calls eventually reach 0.
The deferred computation is the addition:
1n + returned value from sumTo(n - 1)Without that addition, the current call would not include its own number in the result.
Function contract
1Function: sumTo(n)
2
3Input:
4 n — a nonnegative integer
5
6Returns:
7 The sum of integers from 1 through n
8
9Mutates:
10 Nothing
11
12Invalid input policy:
13 Reject n when n is negative or not an integer11 function sumTo(n):
22 if n is not an integer or n < 0:
33 reject input
44
55 if n == 0:
66 return 0
77
88 smallerSum <- sumTo(n - 1)
99 return n + smallerSumThe helper contract is the same function contract: line 8 calls sumTo with n - 1, which must be a nonnegative integer.
For a valid call with n > 0:
n with that smaller answer.Trace the original input:
1sumTo(3)| Active call | Line | Condition or action | Stack state |
|---|---|---|---|
sumTo(3) | 2 | 3 is an integer and not negative | sumTo(3) |
sumTo(3) | 5 | 3 == 0 is false | sumTo(3) |
sumTo(3) | 8 | calls sumTo(2) | sumTo(3): 3 + ... |
sumTo(2) | 2 | 2 is an integer and not negative | sumTo(3): 3 + ..., sumTo(2) |
sumTo(2) | 5 | 2 == 0 is false | sumTo(3): 3 + ..., sumTo(2) |
sumTo(2) | 8 | calls sumTo(1) | sumTo(3): 3 + ..., sumTo(2): 2 + ... |
sumTo(1) | 2 | 1 is an integer and not negative | sumTo(3): 3 + ..., sumTo(2): 2 + ..., sumTo(1) |
sumTo(1) | 5 | 1 == 0 is false | sumTo(3): 3 + ..., sumTo(2): 2 + ..., sumTo(1) |
sumTo(1) | 8 | calls sumTo(0) | sumTo(3): 3 + ..., sumTo(2): 2 + ..., sumTo(1): 1 + ... |
sumTo(0) | 2 | 0 is an integer and not negative | all four calls are active |
sumTo(0) | 5 | 0 == 0 is true | all four calls are active |
sumTo(0) | 6 | returns 0 | sumTo(0) ends |
| Resuming call | Line | smallerSum receives | Returned value |
|---|---|---|---|
sumTo(1) | 8 | 0 | not returned yet |
sumTo(1) | 9 | — | 1 + 0 = 1 |
sumTo(2) | 8 | 1 | not returned yet |
sumTo(2) | 9 | — | 2 + 1 = 3 |
sumTo(3) | 8 | 3 | not returned yet |
sumTo(3) | 9 | — | 3 + 3 = 6 |
1sumTo(3) returns 6We show that sumTo(n) returns the sum of integers from 1 through n for every valid nonnegative integer n.
When n == 0, line 6 returns 0.
The sum of integers from 1 through 0 is an empty sum, and its value is 0. Therefore, sumTo(0) satisfies the contract.
Consider a valid input n > 0.
Line 8 calls:
1sumTo(n - 1)Because n > 0, n - 1 is nonnegative and remains in the valid input domain. It is also strictly smaller than n.
Assume the smaller call returns the sum from 1 through n - 1. Line 9 returns:
1n + smallerSumSubstituting the smaller call’s result gives:
That expression is exactly:
So the current call fulfills its responsibility.
For every non-base call, the input changes from n to n - 1.
Starting from any nonnegative integer, repeatedly subtracting 1 eventually reaches 0. At 0, the base case returns instead of making another recursive call.
Therefore, the function terminates for every valid input and returns the required sum.
For input n, the calls are:
1sumTo(n), sumTo(n - 1), ..., sumTo(1), sumTo(0)There is one call for each value from n down to 0.
That gives:
Each call does constant nonrecursive work:
n == 0,The total time is:
At the deepest point, the active stack contains calls for:
1n, n - 1, ..., 0There are n + 1 active call frames at that point. The auxiliary call-stack space is:
The function does not create an input-sized data structure. Its auxiliary space comes from recursion frames.
Incorrect recursive line:
1smallerSum <- sumTo(n)Smallest exposing input:
1sumTo(1)Wrong state:
1sumTo(1) calls sumTo(1)
2sumTo(1) calls sumTo(1)
3sumTo(1) calls sumTo(1)
4...The input never becomes smaller, so the base case is never reached. The result is nontermination.
Correction:
1smallerSum <- sumTo(n - 1)Now the input moves from 1 to 0.
Incorrect line:
1return sumTo(n - 1)Exposing input:
1sumTo(3)Wrong return sequence:
1sumTo(0) returns 0
2sumTo(1) returns 0
3sumTo(2) returns 0
4sumTo(3) returns 0The recursive call solves only the smaller range. The current value n must still be added.
Correction:
1smallerSum <- sumTo(n - 1)
2return n + smallerSum1 for the base caseIncorrect base case:
1if n == 0:
2 return 1Smallest exposing input:
1sumTo(1)Wrong calculation:
1sumTo(1) = 1 + sumTo(0)
2 = 1 + 1
3 = 2The empty sum must be 0.
Correction:
1if n == 0:
2 return 0Incorrect assumption:
1Negative values can use the same recurrence without special handling.Exposing input:
1sumTo(-1)Wrong state if the function keeps recursing:
1sumTo(-1) calls sumTo(-2)
2sumTo(-2) calls sumTo(-3)
3...The input moves away from the base case.
Correction: define the valid domain as nonnegative integers and reject or otherwise handle invalid input according to the chosen API policy.
Implement sumTo(n) for nonnegative integer n.
The executable tests will verify this contract:
1sumTo(0) == 0
2sumTo(1) == 1
3sumTo(3) == 6
4sumTo(10) == 55Your implementation must preserve the lesson’s function contract: accept nonnegative integer n, return the sum from 1 through n, use a base case for 0, make the recursive request on n - 1 when n > 0, and add n after the smaller call returns.
1def sum_to(n):
2 if not isinstance(n, int) or n < 0:
3 raise ValueError("n must be a nonnegative integer")
4 if n == 0:
5 return 0 # base case: the empty sum
6 smaller_sum = sum_to(n - 1) # smaller subproblem
7 return n + smaller_sum # deferred work after the call returns
8
9print(sum_to(0), sum_to(1), sum_to(3), sum_to(10))1public class Main {
2 static int sumTo(int n) {
3 if (n < 0) throw new IllegalArgumentException("n must be nonnegative");
4 if (n == 0) return 0; // base case: the empty sum
5 int smallerSum = sumTo(n - 1); // smaller subproblem
6 return n + smallerSum; // deferred work after the call returns
7 }
8
9 public static void main(String[] args) {
10 System.out.println(sumTo(0) + " " + sumTo(1) + " " + sumTo(3) + " " + sumTo(10));
11 }
12}1#include <iostream>
2#include <stdexcept>
3using namespace std;
4
5int sumTo(int n) {
6 if (n < 0) throw invalid_argument("n must be nonnegative");
7 if (n == 0) return 0; // base case: the empty sum
8 int smallerSum = sumTo(n - 1); // smaller subproblem
9 return n + smallerSum; // deferred work after the call returns
10}
11
12int main() {
13 cout << sumTo(0) << " " << sumTo(1) << " " << sumTo(3) << " " << sumTo(10) << endl;
14}1function sumTo(n) {
2 if (!Number.isInteger(n) || n < 0) throw new RangeError('n must be a nonnegative integer');
3 if (n === 0) return 0; // base case: the empty sum
4 const smallerSum = sumTo(n - 1); // smaller subproblem
5 return n + smallerSum; // deferred work after the call returns
6}
7
8console.log([sumTo(0), sumTo(1), sumTo(3), sumTo(10)].join(' '));It is solving a problem by asking the same function for a smaller version of it. sumTo(3) asks for sumTo(2), adds 3 to the answer, and returns 6. The chain ends at sumTo(0), which returns 0 without asking anyone.
Summing 1 through n, factorial, and Fibonacci all follow the same shape. Walking an array by index and the recursive tree traversals do too. Each has a base case and a call on a strictly smaller input.
A base case that returns directly, and a recursive case that calls the function on a smaller valid input. The size measure, here n, must shrink on every call. Otherwise the base case is never reached.
It never terminates. With sumTo(1) calling sumTo(1), the argument never shrinks and frames pile up until the runtime stops it, for example with a RecursionError in Python or a StackOverflowError in Java.
Both can cost O(n) time here, but the recursive sumTo also holds n + 1 stack frames, while a loop needs O(1) extra space. Use recursion when the problem is naturally self-similar, such as trees, and a loop when it is a flat count.