15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A base case is an input a recursive function answers directly, with no further call. The recursive case reduces every other input to a smaller valid one. Together they must cover every valid input, and each call must move toward the base case. In factorial, n == 0 returns 1 and n > 0 returns n times factorial(n - 1).
| Base case (factorial) | n = 0 returns 1, because the factorial of 0 is defined as 1 |
|---|---|
| Recursive case (factorial) | n > 0 returns n x factorial(n - 1) |
| Cases must be | Complete and mutually exclusive over the valid inputs |
| Calls for input n | n + 1 calls, n multiplications |
| Time and stack space | O(n) time, O(n) auxiliary stack space |
Assume you can describe a recursive function as a function that may call itself on a smaller input.
Define factorial only for nonnegative integers:
0! = 1n > 0, n! = n × (n - 1)!The first rule handles an input directly. The second rule reduces the problem.
Why does factorial(0) return 1? Because 0! is defined as 1. It is also the value that makes the recursive definition work at n = 1:
For an input outside this contract, such as factorial(-1), the caller must reject it or use a separately documented policy. Factorial for negative integers is outside this lesson's contract.
Start with:
The definition gives:
Then:
Then:
Finally, the input is handled directly:
There are two cases.
| Input condition | Action | Case name |
|---|---|---|
n = 0 | Return 1 | Base case |
n > 0 | Return n × factorial(n - 1) | Recursive case |
A base case is an input handled without another recursive call.
A recursive case reduces an input to a smaller valid instance of the same problem.
The branch conditions cover every valid input:
0 or greater than 0.0 and greater than 0.The cases are complete and mutually exclusive.
A recursive call creates a new active function call. For factorial(3), follow the calls downward first.
| Active call | Matches | Requested work |
|---|---|---|
factorial(3) | Recursive case | 3 × factorial(2) |
factorial(2) | Recursive case | 2 × factorial(1) |
factorial(1) | Recursive case | 1 × factorial(0) |
factorial(0) | Base case | Return 1 |
Now the waiting multiplications resolve upward.
| Returning from | Returned value | Waiting expression becomes |
|---|---|---|
factorial(0) | 1 | factorial(1) = 1 × 1 = 1 |
factorial(1) | 1 | factorial(2) = 2 × 1 = 2 |
factorial(2) | 2 | factorial(3) = 3 × 2 = 6 |
The full sequence is:
factorial(3) matches the recursive case and requests 3 × factorial(2).factorial(2) matches the recursive case and requests 2 × factorial(1).factorial(1) matches the recursive case and requests 1 × factorial(0).factorial(0) matches the base case and returns 1.factorial(0) resolves factorial(1) = 1.factorial(1) resolves factorial(2) = 2.factorial(2) resolves factorial(3) = 6.Every call in the trace has a nonnegative integer argument:
factorial(3)factorial(2)factorial(1)factorial(0)Every recursive call reduces its argument by exactly one.
Every call
factorial(k)haskas a nonnegative integer, and each recursive call changesktok - 1, so the call sequence must eventually reachk = 0.
That statement is the recursion invariant.
For a positive k, the next argument is k - 1.
k = 3, the next argument is 2.k = 2, the next argument is 1.k = 1, the next argument is 0.Nonnegative integers cannot decrease by one forever, so the calls eventually reach 0. At 0, the function stops recursing.
The number n is the termination measure. Each recursive call makes that measure smaller.
Derive the function from its contract.
0, return the defined value of 0!, which is 1.n! = n × (n - 1)!.n - 1.The algorithm needs one conditional:
n == 0 identifies the base case.n > 0.The stopping condition and reducing condition must be correct together.
If the function stopped only at n == 1, then factorial(0) would not have a valid branch. If the recursive call used factorial(n), the input would never get closer to the base case.
Function contract
n, a nonnegative integer.n!, the factorial of n.n or any external data.n = 0 is valid and returns 1.1FUNCTION factorial(n)
2 INPUT: n, a nonnegative integer
3 OUTPUT: n!
4 MUTATION: none
5
61. IF n == 0 THEN
72. RETURN 1
83. END IF
94. RETURN n × factorial(n - 1)
10END FUNCTIONThere is no helper function.
Line 1 is the base-case test. If it succeeds, line 2 returns immediately. Line 4 is the recursive case. It is reached only when n > 0, because the input is within the nonnegative-integer contract and n was not 0.
Use the same input:
1factorial(3)| Active call | Line | Result |
|---|---|---|
factorial(3) | 1 | 3 == 0 is false |
factorial(3) | 4 | Must return 3 × factorial(2); call factorial(2) |
factorial(2) | 1 | 2 == 0 is false |
factorial(2) | 4 | Must return 2 × factorial(1); call factorial(1) |
factorial(1) | 1 | 1 == 0 is false |
factorial(1) | 4 | Must return 1 × factorial(0); call factorial(0) |
factorial(0) | 1 | 0 == 0 is true |
factorial(0) | 2 | Return 1 |
At this point, no more recursive calls are made.
| Waiting call | Returned recursive value | Line 4 resolves to | Returned value |
|---|---|---|---|
factorial(1) | 1 | 1 × 1 | 1 |
factorial(2) | 1 | 2 × 1 | 2 |
factorial(3) | 2 | 3 × 2 | 6 |
1factorial(3) returns 6The boundary case follows the base branch immediately:
1factorial(0)0 == 0 is true.1.Show two things:
For n = 0, line 1 is true, so line 2 returns 1.
The factorial definition states:
The base case returns the correct value and does not recurse when n = 0.
Assume n > 0. Line 1 is false, so the function reaches line 4:
Because n > 0, n - 1 is a nonnegative integer. The recursive call remains inside the function's valid domain.
Assume that factorial(n - 1) correctly returns:
Then line 4 returns:
By the factorial definition for positive n, this equals:
If the smaller call is correct, the current call is also correct.
The base case establishes correctness at 0. The recursive case extends correctness from n - 1 to n. Therefore, factorial(n) returns n! for every nonnegative integer n.
The initial call has a nonnegative integer argument n.
Each recursive call changes the argument from k to k - 1. Recursion occurs only for k > 0, so the next argument remains a nonnegative integer.
The argument decreases by one at every recursive level:
Eventually it reaches 0, where the base case returns without another recursive call. Therefore, the algorithm terminates.
For input n, the parameter takes these values:
That produces n + 1 calls total.
For example, factorial(3) creates four calls:
1factorial(3)
2factorial(2)
3factorial(1)
4factorial(0)Each call performs one comparison:
1n == 0There are n + 1 comparisons.
Every non-base call also performs one multiplication when its recursive call returns. There are n positive inputs from n down to 1, so there are n multiplications.
The total work grows linearly with n:
While the function is moving downward, earlier calls remain active and wait for the recursive result. The maximum active depth is:
So the auxiliary stack space is:
Auxiliary stack space is separate from the input and the returned number.
Incorrect line
1IF n == 0 THEN
2 RETURN 0Smallest exposing input
1factorial(1)Wrong state and result
1factorial(1)
2= 1 × factorial(0)
3= 1 × 0
4= 0But 1! must be 1.
Correction
1RETURN 1Incorrect line
1RETURN n × factorial(n)Smallest exposing input
1factorial(1)Wrong state and result
With the bug, factorial(1) calls factorial(1) again and again. The argument never changes, so the stack keeps growing and never reaches the base case 0.
The argument never changes. The call never reaches 0, so the result is nontermination.
Correction
1RETURN n × factorial(n - 1)Incorrect line
1IF n == 1 THEN
2 RETURN 1Smallest exposing input
1factorial(0)Wrong state and result
factorial(0) does not match the stopping condition. It reaches the recursive expression and attempts factorial(-1), or otherwise fails under the nonnegative-integer contract.
Correction
Include n == 0 as the base case:
1IF n == 0 THEN
2 RETURN 1Incorrect line
1RETURN n + factorial(n - 1)Exposing input
1factorial(3)Wrong state and result
1factorial(3)
2= 3 + factorial(2)
3= 3 + (2 + factorial(1))
4= 3 + (2 + (1 + factorial(0)))
5= 3 + 2 + 1 + 1
6= 7But 3! is 6.
Correction
Use the multiplication from the factorial definition:
1RETURN n × factorial(n - 1)| Input | Expected result or policy |
|---|---|
factorial(0) | Returns 1 |
factorial(1) | Returns 1 |
factorial(3) | Returns 6 |
factorial(-1) | Outside the contract; reject it or apply a documented policy |
Implement factorial(n) for nonnegative integer n so executable tests verify:
1factorial(0) == 1
2factorial(1) == 1
3factorial(3) == 6
4factorial(5) == 120The tested contract is:
n.n!.factorial(0) returns 1.n > 0, return n × factorial(n - 1).n - 1.1def factorial(n):
2 if n == 0:
3 return 1 # base case: factorial of 0 is 1
4 return n * factorial(n - 1) # recursive case: smaller valid input
5
6print(factorial(0), factorial(1), factorial(3), factorial(5))1public class Main {
2 static long factorial(int n) {
3 if (n == 0) return 1; // base case: 0! = 1
4 return n * factorial(n - 1); // recursive case: smaller valid input
5 }
6
7 public static void main(String[] args) {
8 System.out.println(factorial(0) + " " + factorial(1) + " " + factorial(3) + " " + factorial(5));
9 }
10}1#include <iostream>
2using namespace std;
3
4long long factorial(int n) {
5 if (n == 0) return 1; // base case: 0! = 1
6 return n * factorial(n - 1); // recursive case: smaller valid input
7}
8
9int main() {
10 cout << factorial(0) << " " << factorial(1) << " " << factorial(3) << " " << factorial(5) << endl;
11}1function factorial(n) {
2 if (n === 0) return 1; // base case: 0! = 1
3 return n * factorial(n - 1); // recursive case: smaller valid input
4}
5
6console.log([factorial(0), factorial(1), factorial(3), factorial(5)].join(' '));Without one, nothing stops the chain of calls. Every call asks for another call, the stack keeps growing, and the function never returns a value. The base case is the only place a recursive function answers without recursing.
It does not terminate. In factorial, replacing n - 1 with n leaves the argument unchanged, so factorial(1) calls factorial(1) forever until the runtime runs out of stack and raises an error.
Because the factorial of 0 is defined as 1. It also keeps the rule working at n = 1, where factorial(1) = 1 x factorial(0) = 1 x 1 = 1. Returning 0 would make every factorial 0.
The same as in any language: the branch that returns without calling the function again. In Python it is usually an if at the top, such as if n == 0: return 1, placed before the recursive return.
Yes. Naive Fibonacci needs two, fib(0) = 0 and fib(1) = 1, because each call reduces n by 1 or 2. Make sure the base cases cover every way the argument can land.