I. In-Class Exercises

Programming Exercises

1. Count the Total Number of Rabbits Each Month: L2041
2. Arithmetic Sequence Last Term Calculation: L2042
3. Tiling a Grid with Dominoes: L2043
4. Count the Number of 3s: L2044

II. Knowledge Summary

✨ Core Idea of Recurrence

The core idea of recurrence is: using known results to derive unknown results step by step.

Here is a real-life example: you are climbing stairs, and at each floor you write down the current floor number on a piece of paper. You do not need to know the 100th floor all at once — you just need to know "what floor was the last one" and add 1. This is the idea behind recurrence: go from the known to the unknown, where each step depends only on previously computed results.

In programming, recurrence is usually expressed as a recurrence relation (also called a recurrence formula), describing "how the n-th term is computed from previous terms." For example:

• Arithmetic sequence: a[n] = a[n-1] + d (each term = previous term + common difference)
• Fibonacci sequence: f[n] = f[n-1] + f[n-2] (each term = sum of the two preceding terms)

✨ Algorithm Principle of Recurrence

Solving with recurrence involves three key elements:

1. Initial values: The starting point of the recurrence — these cannot be computed by the formula and must be directly given. For example, the Fibonacci sequence has f[0]=1, f[1]=1.
2. Recurrence formula: Describes the relationship between the "current term" and "previous terms." For example, f[n] = f[n-1] + f[n-2].
3. Direction of progression: Starting from the initial values, compute step by step in order until the target result is reached.

General pattern for implementing recurrence with a loop:

1// Step 1: Set initial values
2f[0] = initial_value;
3
4// Step 2: Use a loop to compute step by step
5for (int i = 1; i < n; i++) {
6    f[i] = compute from f[i-1] and other known terms using the recurrence formula;
7}
8
9// Step 3: f[n-1] is the final result

Difference between recurrence and direct computation: Some problems can be solved in one step using a mathematical formula (e.g., the arithmetic series sum formula n*(n+1)/2), but many problems lack such a "universal formula." The advantage of recurrence is: as long as you can find the relationship between adjacent terms, you can derive the answer step by step, without needing a closed-form formula.

Common scenarios where recurrence is used:

1. Sequence computation: Such as arithmetic sequences, geometric sequences, Fibonacci sequences, etc.
2. Greedy problems: Deriving the global optimum from local optima
3. Dynamic programming problems: Deriving the solution to the original problem from sub-problem solutions

For now, this lesson focuses on sequence computation.

✨ Recurrence Examples

Arithmetic Sequence

Recurrence formula: a[n] = a[n - 1] + d

a[0] = 0;
for (int i = 1; i < n; i++) { // Note: when using i-1 as an index, the loop should start from 1
    a[i] = a[i - 1] + d;
}

Geometric Sequence

Recurrence formula: a[n] = a[n-1] * q

a[0] = 1;
for (int i = 1; i < n; i++) { // Note: when using i-1 as an index, the loop should start from 1
    a[i] = a[i - 1] * q;
}

Fibonacci Sequence

Recurrence formula: f[n] = f[n-1] + f[n-2]

f[0] = 1;
f[1] = 1;
for (int i = 2; i < n; i++) { // Note: when using i-2 as an index, the loop should start from 2
    f[i] = f[i - 1] * f[n - 2];
}

✨ Recurrence for Summation

Sum formula: sum(n) = n + (n - 1) + (n - 2) + ... + 3 + 2 + 1

Recurrence formula: s[n] = s[n-1] + n

s[0] = 0;
for (int i = 1; i < n; i++) { // Note: when using i-1 as an index, the loop should start from 1
    s[i] = s[i - 1] + i;
}

✨ Recurrence for Factorial

Factorial formula: n! = n x (n - 1) x (n - 2) x ... x 3 x 2 x 1

Recurrence formula: f[n] = f[n-1] * n

f[0] = 0;
for (int i = 1; i < n; i++) { // Note: when using i-1 as an index, the loop should start from 1
    f[i] = f[i - 1] * i;
}

✨ Execution Example of Recurrence

Using the Fibonacci sequence as an example, here is the complete execution process of recurrence.

Problem: Find the first 8 terms of the Fibonacci sequence.

Recurrence formula: f[n] = f[n-1] + f[n-2], where f[0]=1, f[1]=1

Step-by-step execution:

The final sequence is: 1, 1, 2, 3, 5, 8, 13, 21

Key observation: Each term depends only on the two preceding terms, so the loop must start from i=2 (to ensure both i-1 and i-2 are valid).

✨ Complexity Analysis of Recurrence

Complexity of recurrence algorithms:

• Time Complexity: O(n) — only one loop from start to end
• Space Complexity: If an array is used to store all intermediate results, it is O(n); if only the previous few terms are kept (e.g., Fibonacci only needs the last two terms), it can be optimized to O(1)

Advantages: Simple to implement, efficient, avoids the redundant computation and stack overhead of recursion. Disadvantages: Requires finding the correct recurrence formula, which may not be easy to discover for some problems.

✨ Detailed Problem-Solving Steps: How to Find the Recurrence Formula

When facing a recurrence problem, follow these steps:

Step 1: Manually compute the first few terms. Calculate the first 4-5 terms by hand and observe the pattern.

Step 2: Look for relationships between adjacent terms. Think about whether the "n-th term" can be expressed using the "(n-1)-th term" or earlier terms.

Step 3: Determine the initial conditions. The recurrence formula needs initial values to start computing — determine the values of f[0], f[1], etc.

Step 4: Verify the formula. Recompute the first few terms using the recurrence formula and check whether they match your manual calculations.

Example: Tiling a Grid with Dominoes

How many ways are there to tile a 2xn grid using 1x2 dominoes?

• n=1: Only one vertical domino, 1 way → f[1]=1
• n=2: Two vertical dominoes or two horizontal dominoes, 2 ways → f[2]=2
• n=3: Add a vertical domino to the n=2 case, or add two horizontal dominoes to the n=1 case → f[3]=f[2]+f[1]=3
• Recurrence formula: f[n] = f[n-1] + f[n-2] (same as the Fibonacci sequence!)

✨ Common Mistakes with Recurrence

1. Wrong loop starting point: When using f[i-1], the loop should start from i=1; when using f[i-2], it should start from i=2. Starting from i=0 would make f[i-1] = f[-1], which is out of bounds.
2. Incorrect initial values: For example, the initial value of factorial should be f[0]=1 (since 0!=1). Writing f[0]=0 would cause all terms to be 0. Note that the f[0] = 0 in the example above is something to be cautious about — factorial should use f[0]=1.
3. Data overflow: Values may grow very quickly during recurrence. For example, factorial grows extremely fast — 20! already exceeds the range of long long. The 47th Fibonacci number also exceeds the int range. When dealing with large numbers, use modular arithmetic or larger data types.
4. Wrong direction of recurrence: Recurrence goes from the known to the unknown. If the formula is f[n] = f[n-1] + f[n-2], you must compute from small to large, not from large to small.

III. Homework

Programming Exercises

1. Square Root: L2045
2. Climbing Stairs: L2046