Introduction to Recursion - Язык программирования C++ для спортивного программирования
Introduction to Recursion
Learn basic concepts of recursion.
Introduction
Recursion is a way to solve a problem by asking the same function to solve a smaller version of that problem. A recursive function calls itself, but each call must move toward a situation that can be answered immediately.
For example, the sum of an array from position i onward can be described as the current value a[i] plus the sum from position i+1 onward. The second part is the same problem with a smaller remaining segment.
Recursion is not only a shorter way to write loops. It is the natural language of tree traversal, depth-first search, divide and conquer, dynamic programming, and backtracking over choices. In those topics, the problem itself is built from smaller copies of the same structure.
Problem and motivation
Given an array a[1…, calculate the sum of all its elements.
n
]
An ordinary loop is the simplest solution, but this task gives us a clean first recursive definition. Let
get_sum(i)
mean the sum of a[i],a[i+1],…,a[n].
If i=n+1, there are no elements left, so the answer is 0. Otherwise, the answer is
get_sum(i)=a[i]+get_sum(i+1)
This definition already contains the complete recursive algorithm.
Iterative approach
We can solve the task with a loop:
This solution is excellent and should normally be preferred for a simple array sum. The recursive version has the same O(n) running time but also uses the call stack. We use it here because its structure clearly demonstrates the ideas that later appear in more naturally recursive problems.
Recursion is a tool, not an automatic optimization. Choose it when it makes the state and transitions easier to express.
Core concept
Every correct recursive solution answers four questions.
What does the function mean?
Before writing code, state the contract of the function in one sentence. For this task:
get_sum(i) returns the sum of the array segment a[i…n].
This meaning tells us what parameters are needed and what the returned value represents. If the function's meaning is unclear, the recursive call will usually be unclear too.
What is the base case?
The base case is a state that does not need another recursive call. Here, when i=n+1, the segment is empty and its sum is 0.
The base case stops the chain of calls. Without it, the function would continue calling itself until the program runs out of stack memory.
How does the problem become smaller?
At position i, we take a[i] and ask for the sum beginning at i+1:
The index increases, so the number of unprocessed elements decreases. Eventually, i reaches n+1. A recursive call must always make measurable progress toward a base case.
How is the smaller answer used?
The recursive call returns the answer for the smaller problem. The current call combines it with its own contribution. Here, that combination is addition.
In other algorithms, the combination may be taking a minimum, merging two sorted halves, trying another choice, or attaching answers from child vertices.
The call stack
When one function calls another, the first function pauses. C++ stores its parameters, local variables, and return position in memory called the call stack. The new function call receives its own separate copy of local variables.
Recursive calls continue being placed on the stack until a base case returns. Then the calls finish in reverse order: the most recent call returns first, followed by the call that was waiting for it.
This creates two natural moments inside a recursive function:
code before the recursive call runs while moving deeper;
code after the recursive call runs while returning upward.
For example:
Calling show(3) prints 3 2 1 1 2 3. The first print happens while calls go down from 3 to 1. The second happens while they return from 1 to 3.
Execution order: before vs. after recursion
The position of statements relative to the recursive call determines whether work is performed on the way down (as the call stack grows) or on the way up (as the call stack unwinds).
Printing from 1 to n (Work on the way up)
When cout is placed after the recursive call, the function descends all the way to the base case first. Printing only occurs as each stack frame returns, producing the output in forward order (1,2,…,n).
Printing 1 to n: Work after recursive call
C++
код · C++строка 10
1void print_1_to_n(int x) {
2 if (x == 0) {
3 return;
4 }
5 print_1_to_n(x - 1);
6 cout << x << " ";
7}
8
9int main() {
10 print_1_to_n(3);
11 return 0;
12}
Call print_1_to_n(3)
L10
main() calls print_1_to_n(3). Execution in main() pauses.
инв
Statements after the recursive call execute in reverse call order as the stack unwinds.
стек вызовов
1main()
2print_1_to_n(3)
x⤳3
depth1
L10
01 / 12
Printing from n to 1 (Work on the way down)
When cout is placed before the recursive call, output is printed immediately upon entering each call before descending further, producing the output in reverse order (n,n−1,…,1).
Printing n to 1: Work before recursive call
C++
код · C++строка 10
1void print_n_to_1(int x) {
2 if (x == 0) {
3 return;
4 }
5 cout << x << " ";
6 print_n_to_1(x - 1);
7}
8
9int main() {
10 print_n_to_1(3);
11 return 0;
12}
Call print_n_to_1(3)
L10
main() calls print_n_to_1(3).
инв
Statements before the recursive call execute in direct call order on the downward path.
стек вызовов
1main()
2print_n_to_1(3)
x⤳3
depth1
L10
01 / 12
Main algorithm
The state is only the first unprocessed position i. The function does not need to pass the current sum downward. Instead, it returns the sum of its segment upward.
Algorithm:
There is one call for each array position and one base-case call. Every call performs constant work, so the total running time is O(n).
Common recursive shapes
One smaller problem
Array sum, factorial, and Euclid's algorithm make one recursive call. The recursion forms a chain.
Several smaller problems
Tree algorithms call the same function for every child. Merge sort recursively solves the left half and the right half. The calls form a tree rather than a chain.
Trying choices and undoing them
Backtracking chooses one option, recurses, then removes that choice before trying another. This is how we generate subsets and permutations. The recursive state represents a partially built answer.
Recursion with repeated states
A direct recursive Fibonacci function calculates the same values many times and takes exponential time. Recursion itself does not prevent repeated work. Dynamic programming adds memoization or a suitable calculation order so that each state is solved once.
Implementation
The input contains n and an array of n integers. The program calculates the sum recursively. The constraint on n should be moderate because the recursion depth is n.
Complexity
Time:O(n) — one call is made for every position.
Memory:O(n) — the deepest moment contains n+1 stack frames.
1. Define get_sum(i):
1.1. If i == n+1, return 0.
1.2. Let remaining_sum = get_sum(i+1).
1.3. Return a[i] + remaining_sum.
2. Read n and a[1..n].
3. Output get_sum(1).
long long sum = 0;for(int i = 1; i <= n; i++){ sum += a[i];}