GESP C++ Level 4 Exam Syllabus Knowledge Points Overview: (6) Recursion Algorithms

In the official GESP C++ Level 4 exam syllabus, there are a total of 11 key points. This article analyzes and introduces the 6th key point.

(6) Master the basic ideas of recursion algorithms, the derivation of recursive relationships, and the solution of recursive problems.

Review of other Level 4 key points:

GESP C++ Level 4 Exam Syllabus Knowledge Points Overview: (1) Pointers

OneCoder, WeChat Official Account: Parent-Child Programming GESP CSP GESP C++ Level 4 Exam Syllabus Knowledge Points Overview: (1) Pointers

GESP C++ Level 4 Exam Syllabus Knowledge Points Overview: (2) Structures and Two-Dimensional Arrays

OneCoder, WeChat Official Account: Parent-Child Programming GESP CSP GESP C++ Level 4 Exam Syllabus Knowledge Points Overview: (2) Structures and Two-Dimensional Arrays

GESP C++ Level 4 Exam Syllabus Knowledge Points Overview: (3) Modularization and Functions

OneCoder, WeChat Official Account: Parent-Child Programming GESP CSP GESP C++ Level 4 Exam Syllabus Knowledge Points Overview: (3) Modularization and Functions

GESP C++ Level 4 Exam Syllabus Knowledge Points Overview: (4) Variables and Scope

OneCoder, WeChat Official Account: Parent-Child Programming GESP CSP GESP C++ Level 4 Exam Syllabus Knowledge Points Overview: (4) Variables and Scope

GESP C++ Level 4 Exam Syllabus Knowledge Points Overview: (5) Value Passing

OneCoder, WeChat Official Account: Parent-Child Programming GESP CSP GESP C++ Level 4 Exam Syllabus Knowledge Points Overview: (5) Value Passing

1. Basic Ideas of Recursion Algorithms

1.1 What is Recursion?

Recursion is an algorithmic strategy that derives unknown values step by step from known values, commonly used to solve problems where the current state depends on the previous one or several states.

1.2 Difference from Recursion

Characteristics	Recursion (Iteration)	Recursion (Recursion)
Implementation Method	Loop	Function calls itself
Calculation Order	Bottom-up	Top-down
Suitable Scenarios	Arrays/Dynamic Programming	Tree Structures, DFS, etc.
Resource Consumption	More space-efficient	Occupies more call stack

1.3 Basic Ideas of Recursion

Basic Idea: First determine the problem’s initial state (boundary condition), then find a rule to derive the next item from known items (recursive relationship), and successively calculate the target item.

2. Steps to Derive Recursive Relationships

🔶 Step 1: Determine State

Use a variable or array to represent a sub-result of the problem.

Example: <span>f[i]</span> represents the i-th step or state of the problem.

🔶 Step 2: Write Initial Conditions (Base Case)

Identify the simplest, known initial values as the starting point for recursion.

🔶 Step 3: Establish Recursive Relationships (Transition)

Analyze the relationship between the current state and previous states, and write the “state transition formula”.

🔶 Step 4: Use Loops to Solve

Utilize loop structures to gradually compute the final result.

3. Examples of Recursive Problems

🌟 Example 1: Fibonacci Sequence

❓ Problem Description:

Define the Fibonacci sequence as follows:

• F(1) = 1
• F(2) = 1
• F(n) = F(n-1) + F(n-2) (n ≥ 3)

Find F(n)

💭 Recursive Analysis:

• State Representation: <span>f[i]</span> represents the value of the i-th item
• Initial Values: <span>f[1] = 1</span>, <span>f[2] = 1</span>
• Recursive Relationship: <span>f[i] = f[i-1] + f[i-2]</span>

💻 C++ Example Code:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int f[100] = {0};
    f[1] = f[2] = 1;
    for (int i = 3; i <= n; i++) {
        f[i] = f[i-1] + f[i-2];
    }
    cout << f[n] << endl;
    return 0;
}

🌟 Example 2: Frog Jumping Stairs

❓ Problem Description:

A frog can jump either 1 or 2 steps at a time. How many ways can it jump to the <span>n</span>th step?

### 💭 Recursive Analysis:

• State Representation: <span>f[i]</span> represents the number of ways to jump to the i-th step

• Initial Values:

• <span>f[0] = 1</span> (jumping 0 steps counts as 1 way)
• <span>f[1] = 1</span>

• Recursive Relationship:

• To reach the <span>i</span>th step, the frog can either jump from the <span>i-1</span>th step or the <span>i-2</span>th step
• Thus, <span>f[i] = f[i-1] + f[i-2]</span>

💻 C++ Example Code:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int f[100] = {0};
    f[0] = 1;
    f[1] = 1;
    for (int i = 2; i <= n; i++) {
        f[i] = f[i-1] + f[i-2];
    }
    cout << f[n] << endl;
    return 0;
}

🌟 Example 3: Complete Knapsack Counting Problem

❓ Problem Description:

There are <span>n</span> types of items, each of which can be selected an unlimited number of times. Given a target volume <span>V</span>, find the number of combinations that sum to volume <span>V</span>.

Input: Item volume array <span>a[1..n]</span>, target volume <span>V</span> Output: Number of combinations

💭 Recursive Analysis:

• State Representation: <span>f[i]</span> represents the number of schemes for volume <span>i</span>
• Initial Value: <span>f[0] = 1</span> (indicating there is only 1 way to achieve a volume of 0—by selecting nothing)
• State Transition: For each item <span>a[i]</span>, update <span>f[v]</span> from small to large:

for i in 1..n:
    for j in a[i]..V:
        f[j] += f[j - a[i]]

💻 C++ Example Code:

#include <iostream>
using namespace std;

int main() {
    int n, V;
    cin >> n >> V;
    int a[100];
    for (int i = 0; i < n; i++) cin >> a[i];

    int f[10001] = {0};
    f[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = a[i]; j <= V; j++) {
            f[j] += f[j - a[i]];
        }
    }
    cout << f[V] << endl;
    return 0;
}

4. Summary: Recursion Modeling Guidelines

“State representation” must be accurate, “initial conditions” must be complete, “transition equations” must be logically clear, and “traversal order” must not be disordered.

5. Recursion and Competitive Programming

In competitions or algorithm problems, mastering the idea of recursion helps to:

• Model problems as state transitions
• Identify efficient iterative computation methods
• Avoid stack overflow and repeated calculations caused by brute-force recursion

Notes:

• Initial values must be correct: Otherwise, recursion will be incorrect.
• Ensure sufficient array space: To avoid out-of-bounds errors.
• Pay attention to boundary handling: Loop ranges must coordinate with initial values.
• Rolling variables can optimize space: If only the last two items are needed, the entire array may not be necessary.

Recursion is a way of thinking that builds from small to large, deriving the unknown from the known, and is very practical in algorithm design. Mastering it requires careful observation and consideration of the relationships between states, and attempting to express the essence of the problem using mathematical rules or state transition formulas.

All code has been uploaded to GitHub: https://github.com/lihongzheshuai/yummy-code

The “luogu-” series problems have been added to LuoguJava, C++ Beginner Team,Assignment List, available for online assessment, team slots are limited, welcome to join.

The “bcqm-” series problems can be assessed online in theProgramming Enlightenment Question Bank.