Recursion
I. In-Class Exercises
Programming Exercises
Recursive Function Expansion
To understand the execution process of recursion, the following examples compare non-function-call approach (manual expansion) and function-call approach (recursion) using a "telling a story" example, demonstrating recursive behavior at different call depths.
Output 1 Time
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // tellStory(1)
6 int n = 1;
7 printf("time %d: ", n);
8 if (n == 0) {
9 printf("end\n");
10 } else {
11 printf("tell you a story:\n");
12 // tellStory(0)
13 int n = 0;
14 printf("time %d: ", n);
15 printf("end\n");
16 }
17 printf("end of %d\n", n);
18 return 0;
19}1#include <bits/stdc++.h>
2using namespace std;
3
4void tellStory(int n) {
5 printf("time %d: ", n);
6 if (n == 0) {
7 printf("end\n");
8 return;
9 }
10 printf("tell you a story:\n");
11 tellStory(n - 1);
12 printf("end of %d\n", n);
13}
14
15int main() {
16 tellStory(1);
17 return 0;
18}Output 2 Times
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // tellStory(2)
6 int n = 2;
7 printf("time %d: ", n);
8 if (n == 0) {
9 printf("end\n");
10 } else {
11 printf("tell you a story:\n");
12 // tellStory(1)
13 int n = 1;
14 printf("time %d: ", n);
15 if (n == 0) {
16 printf("end\n");
17 } else {
18 printf("tell you a story:\n");
19 // tellStory(0)
20 int n = 0;
21 printf("time %d: ", n);
22 printf("end\n");
23 }
24 printf("end of %d\n", n);
25 }
26 printf("end of %d\n", n);
27 return 0;
28}1#include <bits/stdc++.h>
2using namespace std;
3
4void tellStory(int n) {
5 printf("time %d: ", n);
6 if (n == 0) {
7 printf("end\n");
8 return;
9 }
10 printf("tell you a story:\n");
11 tellStory(n - 1);
12 printf("end of %d\n", n);
13}
14
15int main() {
16 tellStory(2);
17 return 0;
18}Output 3 Times
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int n = 3;
6 printf("time %d: ", n);
7 if (n == 0) {
8 printf("end\n");
9 } else {
10 printf("tell you a story:\n");
11 // tellStory(2)
12 int n = 2;
13 printf("time %d: ", n);
14 if (n == 0) {
15 printf("end\n");
16 } else {
17 printf("tell you a story:\n");
18 // tellStory(1)
19 int n = 1;
20 printf("time %d: ", n);
21 if (n == 0) {
22 printf("end\n");
23 } else {
24 printf("tell you a story:\n");
25 // tellStory(0)
26 int n = 0;
27 printf("time %d: ", n);
28 printf("end\n");
29 }
30 printf("end of %d\n", n);
31 }
32 printf("end of %d\n", n);
33 }
34 printf("end of %d\n", n);
35 return 0;
36}1#include <bits/stdc++.h>
2using namespace std;
3
4void tellStory(int n) {
5 printf("time %d: ", n);
6 if (n == 0) {
7 printf("end\n");
8 return;
9 }
10 printf("tell you a story:\n");
11 tellStory(n - 1);
12 printf("end of %d\n", n);
13}
14
15int main() {
16 tellStory(3);
17 return 0;
18}Recursive Execution of tellStory(3)
From the code expansions above, you can see that each recursive function call "nests" one layer deeper. The sequence diagram below visually shows the complete execution of tellStory(3) — first diving layer by layer, then returning layer by layer:
Recursion (Factorial) - Function Call vs Non-Function Call Comparison
Below, the factorial example further compares recursive functions with manual expansion. As the factorial number increases, the manually expanded code becomes increasingly complex, while the recursive function remains concise.
Factorial of 2
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int factorialN;
6 int n = 2;
7 if (n == 1) {
8 factorialN = 1;
9 } else {
10 {
11 int n = 1;
12 if (n == 1) {
13 factorialN = 1;
14 }
15 }
16 factorialN = n * factorialN;
17 }
18 cout << factorialN << endl;
19 return 0;
20}1#include <bits/stdc++.h>
2using namespace std;
3
4int factorial(int n) {
5 if (n == 1) {
6 return 1;
7 }
8 return n * factorial(n - 1);
9}
10
11int main() {
12 int factorialN = factorial(2);
13 cout << factorialN << endl;
14 return 0;
15}Factorial of 3
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int factorialN = 0;
6 int n = 3;
7 if (n == 1) {
8 factorialN = 1;
9 } else {
10 {
11 int n = 2;
12 if (n == 1) {
13 factorialN = 1;
14 } else {
15 {
16 int n = 1;
17 if (n == 1) {
18 factorialN = 1;
19 }
20 }
21 factorialN = n * factorialN;
22 }
23 }
24 factorialN = n * factorialN;
25 }
26 cout << factorialN << endl;
27 return 0;
28}1#include <bits/stdc++.h>
2using namespace std;
3
4int factorial(int n) {
5 if (n == 1) {
6 return 1;
7 }
8 return n * factorial(n - 1);
9}
10
11int main() {
12 int factorialN = factorial(3);
13 cout << factorialN << endl;
14 return 0;
15}Factorial of 4
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int factorialN = 0;
6 int n = 4;
7 if (n == 1) {
8 factorialN = 1;
9 } else {
10 {
11 int n = 3;
12 if (n == 1) {
13 factorialN = 1;
14 } else {
15 {
16 int n = 2;
17 if (n == 1) {
18 factorialN = 1;
19 } else {
20 {
21 int n = 1;
22 if (n == 1) {
23 factorialN = 1;
24 }
25 }
26 factorialN = n * factorialN;
27 }
28 }
29 factorialN = n * factorialN;
30 }
31 }
32 factorialN = n * factorialN;
33 }
34 cout << factorialN << endl;
35 return 0;
36}1#include <bits/stdc++.h>
2using namespace std;
3
4int factorial(int n) {
5 if (n == 1) {
6 return 1;
7 }
8 return n * factorial(n - 1);
9}
10
11int main() {
12 int factorialN = factorial(4);
13 cout << factorialN << endl;
14 return 0;
15}Recursive Execution of factorial(4)
The sequence diagram below shows the complete recursive process of factorial(4) — first diving layer by layer, then returning with computed results:
II. Knowledge Summary
✨ Core Concept of Recursion
Recursion is a problem-solving approach that uses a function calling itself to iteratively solve problems. It is typically used for problems that can be solved by gradually reducing the problem size.
Common scenarios where recursion is used:
- Problems with clear recurrence relations
- Problems requiring a divide and conquer approach
- Data structure operations (such as tree traversal)
The function used in a recursive process is called a recursive function. A recursive function must contain two parts:
- Base Case: The condition that stops the recursive calls, preventing infinite recursion
- Recursive Case: The part where the function calls itself, reducing the problem size with each call
Execution Flow of a Recursive Function
The flowchart below shows the general execution logic of a recursive function — each call first checks whether the base case is reached; if so, it returns the result directly; otherwise, it reduces the problem size, recursively calls itself, and finally combines the results to return:
✨ Recursion and the Call Stack
What Is the Call Stack?
When a function calls another function (or calls itself), the computer pushes the current function's state (local variables, execution position, etc.) onto the call stack. After the called function returns, the state is popped from the stack to resume execution. Each level of recursive call adds a new layer to the stack, like stacking plates higher and higher.
Using the factorial(4) example from class, the call stack changes as follows:
Forward Phase (Call Stack Expansion)
| Step | Call | Value of n | Base case reached? | Action |
|---|---|---|---|---|
| 1 | factorial(4) | 4 | No | Need to compute 4 * factorial(3), waiting for factorial(3) result |
| 2 | factorial(3) | 3 | No | Need to compute 3 * factorial(2), waiting for factorial(2) result |
| 3 | factorial(2) | 2 | No | Need to compute 2 * factorial(1), waiting for factorial(1) result |
| 4 | factorial(1) | 1 | Yes | Base case reached, return 1 directly |
Return Phase (Layer-by-Layer Return)
| Step | Return Layer | Computation | Return Value |
|---|---|---|---|
| 5 | factorial(1) | Base case | 1 |
| 6 | factorial(2) | 2 * factorial(1) = 2 * 1 | 2 |
| 7 | factorial(3) | 3 * factorial(2) = 3 * 2 | 6 |
| 8 | factorial(4) | 4 * factorial(3) = 4 * 6 | 24 |
Final result: factorial(4) = 24
Call Stack Depth Changes
Below is a more intuitive way to show how the stack depth changes during recursive calls — each level of indentation represents a new function call layer on the stack; deeper means a taller stack:
1factorial(4) called <- Stack depth 1
2|
3+-- factorial(3) called <- Stack depth 2
4| |
5| +-- factorial(2) called <- Stack depth 3
6| | |
7| | +-- factorial(1) called <- Stack depth 4 (deepest)
8| | | +-- return 1
9| | |
10| | +-- return 2*1 = 2
11| |
12| +-- return 3*2 = 6
13|
14+-- return 4*6 = 24Stack depth = number of recursive levels. If the recursion goes too deep (e.g., factorial(100000)), the call stack will exceed the system limit, causing a Stack Overflow.
Recursion is like "Russian nesting dolls": you open layer after layer going inward until you reach the innermost one (base case), then close them from inside out (returning results).
✨ Linear Recursion vs Branching Recursion
The tellStory and factorial examples from class are linear recursion — each call invokes itself only once, forming a straight call chain. But some problems require calling itself multiple times per invocation, forming branching recursion (tree recursion).
Linear Recursion: Factorial
Each call has only one recursive invocation, forming a straight chain:
factorial(4) -> factorial(3) -> factorial(2) -> factorial(1)
Time complexity O(n), call stack depth O(n).
Branching Recursion: Fibonacci Sequence
In the Fibonacci sequence, each term equals the sum of the two preceding terms: f[n] = f[n - 1] + f[n - 2]
1int fibonacci(int n) {
2 if (n == 1 || n == 2) {
3 return 1;
4 }
5 return fibonacci(n - 1) + fibonacci(n - 2);
6}Each call has two recursive invocations, forming a recursion tree — each node splits into two sub-problems:
Nodes of the same color indicate redundant computation: fib(3) is computed 2 times (yellow), fib(2) is computed 3 times (blue). As n grows, the number of tree nodes doubles, giving a time complexity of O(2^n).
The sequence diagram below shows the complete call and return order of fibonacci(5):
Comparison Summary
| Linear Recursion (Factorial) | Branching Recursion (Fibonacci) | |
|---|---|---|
| Recursive calls per invocation | 1 | 2 |
| Call structure | Straight chain | Tree-shaped |
| Time complexity | O(n) | O(2^n) |
| Redundant computation | None | Significant |
✨ Recursion Examples
Arithmetic Sequence
In an arithmetic sequence, the difference between each term and the previous term is a constant d.
Recurrence relation: a[n] = a[n - 1] + d
1int a(int n) {
2 if (n == 1) {
3 return 1;
4 }
5 return a(n - 1) + d;
6}Geometric Sequence
In a geometric sequence, the ratio between each term and the previous term is a constant q.
Recurrence relation: a[n] = a[n - 1] * q
1int a(int n) {
2 if (n == 1) {
3 return 1;
4 }
5 return a(n - 1) * q;
6}Recursive Summation
Find the cumulative sum from 1 to n: sum(n) = n + (n - 1) + ... + 2 + 1
Recurrence relation: s[n] = s[n - 1] + n
1int sum(int n) {
2 if (n == 1) {
3 return 1;
4 }
5 return sum(n - 1) + n;
6}✨ Problem-Solving Steps for Recursion
Example: Use recursion to compute 1+2+3+...+n
Steps:
- Find the recurrence relation:
sum(n) = sum(n-1) + n— the sum of the first n numbers equals the sum of the first n-1 numbers plus n - Determine the base case: When n=1,
sum(1) = 1, no further recursion needed - Write the recursive function:
- Base case:
if (n == 1) return 1; - Recursive case:
return sum(n - 1) + n;
- Base case:
- Verify correctness: Manually trace sum(3)
- sum(3) = sum(2) + 3 = (sum(1) + 2) + 3 = (1 + 2) + 3 = 6
General template for writing recursive functions:
Step 1: Clarify what the function does (what goes in, what comes out)
Step 2: Find the recurrence relation (how to break a large problem into smaller ones)
Step 3: Determine the base case (the smallest problem, with a direct answer)✨ Common Mistakes with Recursion
- Forgetting the base case: Without a termination condition like
if (n == 1) return 1;, the function calls itself infinitely, eventually causing a Stack Overflow crash - Incorrect base case: For example, writing
if (n == 0) return 0;in a factorial function — since 0! = 1, not 0, all results become 0 - Wrong recursion direction: The problem size is not reduced — for example, writing
factorial(n + 1)instead offactorial(n - 1), which also leads to infinite recursion - Redundant computation: In naive Fibonacci recursion,
fibonacci(5)computesfibonacci(3)twice andfibonacci(2)three times, which is very inefficient. For large n (e.g., n=40), the program becomes extremely slow - Confusing iteration and recursion: Iteration uses loops to compute forward, while recursion uses functions to decompose backward. They have opposite approaches but produce the same results — be aware of when to use each