Skip to content

📘 Master Guide to Logical Or Virtual Recursion

1. What is Recursion? (The Basics) 🌱

Before we dive into complex math, let's understand recursion simply. Recursion is just a way of solving a problem by breaking it down into smaller versions of the same problem.

  • The Concept: Imagine you want to calculate the sum of numbers from \(1\) to \(n\) (\(S_n\)). Instead of adding them all at once (\(1+2+3+4...\)), we can define it based on the previous sum.

  • The Logic: The sum of numbers up to \(n\) is just the number \(n\) plus the sum of everything before it (\(n-1\)).

The Formula: \(S(n) = S(n-1) + n\)

The Base Case (Where we stop): \(S(0) = 0\)

Steps for \(S(5)\):

  1. \(S(5) = S(4) + 5\)
  2. \(S(4) = S(3) + 4\)
  3. ...and so on until \(S(0)\).

2. Types of Recursion: Structural vs. Virtual 🆚

It is crucial to know the difference between how a computer "sees" recursion and how a mathematician "sees" it.

🅰️ Structural Recursion (The "Computer Science" Way)

  • Focus: Nodes, Trees, Graphs, Filesystems.
  • How it works: You traverse a structure. Every node looks the same (has the same schema) but holds different data.
  • Example: Searching for a file in a folder. If you find a sub-folder, you "recurse" into it.

🅱️ Virtual / Logical Recursion (The "Mathematical" Way) 🧮

  • Focus: Equations, Formulas, Relationships.
  • How it works: You don't traverse a physical structure. Instead, you hold the mathematical information of a state and derive the next state using a formula.
  • Key Characteristic: It relies on Linear Relationships. \(F(n) = a \cdot F(n-1) + b \cdot F(n-2) \dots\)

💡 Key Takeaway: In Virtual Recursion, we often don't need to "simulate" the whole process step-by-step. If we know the formula (the relationship), we can jump straight to the answer or use shortcuts!

3. Recursion: The Mathematician's Secret Weapon 🧮

Recursion isn't just code; it is the foundation of high-level mathematics. We use it for Proof, Derivation, and Simplification.

I. Proof: Mathematical Induction 🛡️

The logic: "If it works for the first one, and one triggers the next, it works for all." Recursion and Induction are the same logic in reverse.

  • Recursion (Top-Down): To solve for \(N\), I need \(N-1\).
  • Induction (Bottom-Up): If I have \(N-1\), I can prove \(N\).

Example: Proving \(S(n) = \frac{n(n+1)}{2}\)

  1. Check \(n=1\): Formula gives \(1\). Correct.
  2. Assume \(n=k\) is true: We assume \(S(k) = \frac{k(k+1)}{2}\).

  3. Prove for \(n=k+1\) (The Recursive Step):

    \(S(k+1) = S(k) + (k+1)\) Substitute the assumption: \(S(k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}\)

    Result: The formula holds for all numbers.

II. Derivation: Building Formulas 🏗️

Sometimes we use recursive thinking to derive a formula from scratch.

Task: Maximum regions formed by \(n\) lines cutting a circle.

  1. Start small: \(n=1 \to 2\), \(n=2 \to 4\), \(n=3 \to 7\).
  2. Find Relation: To get the \(n\)-th count, we take the previous count and add \(n\). \(f(n) = f(n-1) + n\)
  3. Derive Formula: Summing this series gives \(f(n) = 1 + \frac{n(n+1)}{2}\).

III. Simplification: The Grid Problem 📉

Scenario: You are at \((0,0)\) and want to go to \((n,m)\). You can only move Right or Down.

The Recursive Insight: To reach \((n,m)\), you must have come from either the Left \((n-1, m)\) or Above \((n, m-1)\).

\(Ways(n, m) = Ways(n-1, m) + Ways(n, m-1)\)

The Formula (Pascal's Triangle): Instead of calculating a massive grid, we realize this structure creates Combinations.

\(Formula = \binom{n+m}{n} = \frac{(n+m)!}{n! \cdot m!}\)

4. Recursion in Probability & Expectation 🎲

In "Virtual Recursion," mathematical values like Expected Value often follow linear recursive rules. Instead of simulating millions of random games, we write the recursive equation and simplify it.

Example Case: The CodeChef Compression Algorithm

Problem: A string of length \(N\) is formed using \(K\) distinct characters. We compress it by replacing blocks of identical characters with (char, length). We need the Expected Length of the compressed string.

The "Virtual Recursion" Approach: Instead of generating strings, let's define \(E(i)\) as the expected compressed length of a string of size \(i\).

  1. Recursive Step: When we add the \(i\)-th character, does it increase the compressed length?

    • If \(S[i] == S[i-1]\), the block continues. Length does not increase.
    • If \(S[i] \neq S[i-1]\), a new block starts. Length increases by \(2\) (1 for char, 1 for count).

  2. Probability: Since characters are chosen uniformly: \(P(S[i] \neq S[i-1]) = \frac{K-1}{K}\)

  3. The Recursive Relation: \(E(i) = E(i-1) + \left( \frac{K-1}{K} \times 2 \right)\) (The expected length at \(i\) is the length at \(i-1\) plus the expected "cost" of the new character)

  4. Base Case: \(E(1) = 2 \quad (\text{"a"} \to \text{"a,1"})\)

  5. Solving the Recursion: Since we add the constant \(\frac{K-1}{K} \times 2\) for every step from \(2\) to \(N\): \(E(N) = 2 + (N-1) \times \frac{K-1}{K} \times 2\)

This demonstrates the power of Virtual Recursion: We turned a complex string generation problem into a simple linear formula: \(O(1)\) solution.

5. The "Find the Pattern" Technique 🕵️‍♂️

Usage: Common in DP and Math Puzzles. When given a strange recursive definition, do not simulate it blindly.

The Methodology:

  1. Calculate Base States: Manually calculate \(f(1), f(2), f(3) \dots\)
  2. Observe: Look at the sequence of numbers generated.
  3. Derive Equation: Find the simple \(n\)-variable equation that fits.

Practice Task: The "Odd/Even" Trap

Problem:

  • \(f(1) = 2\)
  • \(f(n) = f(n-1) + 1\) (if \(n\) is even)
  • \(f(n) = f(n-2) + 2\) (if \(n\) is odd and \(> 1\))

Goal: Find \(f(2017)\).

Solution:

  • \(n=1 \rightarrow f(1) = 2\)
  • \(n=2 \rightarrow f(2) = f(1) + 1 = 3\)
  • \(n=3 \rightarrow f(3) = f(1) + 2 = 4\)
  • \(n=4 \rightarrow f(4) = f(3) + 1 = 5\)

Pattern: \(2, 3, 4, 5 \dots \implies f(n) = n + 1\).

Answer: \(f(2017) = \mathbf{2018}\).

5.1 Usage in Common DP States (The "Black Box" Trick) 📦

This is a powerful trick for Competitive Programming. Even if you don't fully understand the combinatorial logic behind a Dynamic Programming (DP) state, you can often "reverse engineer" the recurrence relation if it is linear.

The "Black Box" Strategy:

  1. Ignore the "Why": Don't get stuck trying to prove the transition logic immediately.
  2. Generate Base States: Manually solve the problem for small \(n\) (e.g., \(n=1, 2, 3, 4\)).
  3. Fit the Equation: Assume a common linear form like \(dp[i] = a \cdot dp[i-1] + b \cdot dp[i-2]\).
  4. Solve for Constants: Use your calculated values to solve for \(a\) and \(b\).

Classic Example: Stirling Numbers of the Second Kind (\(S(n, k)\))

  • Problem: Number of ways to partition a set of \(n\) elements into \(k\) non-empty subsets.

  • Small Values (Fixed \(k=2\)):

    • \(n=2\): \(\{ \{A\}, \{B\} \}\) (1 way)
    • \(n=3\): \(\{ \{A,B\}, \{C\} \}\), \(\{ \{A,C\}, \{B\} \}\), \(\{ \{B,C\}, \{A\} \}\) (3 ways)
    • \(n=4\): (7 ways)

  • The Pattern: \(1, 3, 7 \dots\) The relationship is \(S(n, 2) = 2 \cdot S(n-1, 2) + 1\).

  • General Recurrence: \(S(n, k) = k \cdot S(n-1, k) + S(n-1, k-1)\).

🚀 Pro Tip (Advanced): If you have a sequence of integers (like the output of your brute force for \(n=1 \dots 10\)) and you suspect a linear relationship, you can use the Berlekamp-Massey Algorithm. This algorithm takes a sequence and automatically computes the shortest linear recurrence that generates it. It basically "solves" the DP logic for you!

6. Advanced Logic: Fibonacci Fast Doubling 🚀

Usage: Finding the \(n\)-th Fibonacci number for huge \(n\) (e.g., \(10^9\)). Standard recursion (\(O(2^n)\)) and linear iteration (\(O(n)\)) are too slow. We use Virtual Recursion formulas derived from matrix exponentiation (\(O(\log n)\)).

The Formulas:

  • Even term: \(F(2k) = F(k) \times (2 \cdot F(k+1) - F(k))\)
  • Odd term: \(F(2k+1) = F(k+1)^2 + F(k)^2\)

C++ Implementation

Click to expand solution code 
#include <iostream>
#include <vector>
using namespace std;

long long MOD = 1e9 + 7;

// Function returns {F(n), F(n+1)}
pair<long long, long long> fib(int n) {
    if (n == 0) return {0, 1}; // Base case

    // Recursively calculate for n/2
    auto p = fib(n >> 1);
    long long c = p.first;  // F(k)
    long long d = p.second; // F(k+1)

    // Apply Fast Doubling Formulas
    long long next_c = (c * ((2 * d % MOD - c + MOD) % MOD)) % MOD; // F(2k)
    long long next_d = (c * c % MOD + d * d % MOD) % MOD;           // F(2k+1)

    if (n & 1)
        return {next_d, (next_c + next_d) % MOD};
    else
        return {next_c, next_d};
}

int main() {
    int n = 10;
    cout << "Fibonacci(" << n << ") = " << fib(n).first << endl;
    return 0;
}

7. Time Complexity (Master Theorem Basics) ⏱️

For many recursive algorithms (especially Divide & Conquer), the complexity isn't obvious. We use the Master Theorem for relations of the form: \(T(n) = aT(n/b) + f(n)\)

  • \(a\): Number of subproblems (branches).
  • \(b\): Factor by which input size shrinks.
  • \(f(n)\): Work done outside the recursive calls (merge/partition step).

Common Examples to Memorize:

  • Merge Sort: \(T(n) = 2T(n/2) + O(n) \to O(n \log n)\)
  • Binary Search: \(T(n) = 1T(n/2) + O(1) \to O(\log n)\)
  • Fibonacci (Naive): \(T(n) = T(n-1) + T(n-2) \to O(2^n)\) (Roughly \(\phi^n\))

8. More similar tasks 🧠

These tasks test your ability to see the "Mathematical Reality" behind the recursive definition. Do not run the code mentally. Find the pattern.

Task 1: The "Powers of Two" Disguise

Problem Statement:

Define a function \(T(n)\) recursively by:

  • \(T(0) = 1\)
  • \(T(n) = 2 \cdot T(n-1) + 1\) (for \(n > 0\))

Goal: Find \(T(10)\).

Solution: 1. Calculate Base States:

  • \(n=0 \rightarrow T(0) = 1\)
  • \(n=1 \rightarrow T(1) = 2(1) + 1 = 3\)
  • \(n=2 \rightarrow T(2) = 2(3) + 1 = 7\)

  • \(n=3 \rightarrow T(3) = 2(7) + 1 = 15\)

  • Observe Pattern: The sequence is \(1, 3, 7, 15 \dots\) Notice that \(1 = 2^1 - 1\), \(3 = 2^2 - 1\), \(7 = 2^3 - 1\).

  • Derive Formula: \(T(n) = 2^{n+1} - 1\).

Final Answer: \(T(10) = 2^{11} - 1 = 2048 - 1 = \mathbf{2047}\)

Task 2: The "Cyclic" Sequence

Problem Statement:

Define a function \(g(n)\) recursively by:

  • \(g(1) = 1\)
  • \(g(2) = 3\)
  • \(g(n) = g(n-1) - g(n-2)\) (for \(n > 2\))

Goal: Find \(g(100)\).

Solution: 1. Calculate Base States:

  • \(n=1 \rightarrow 1\)
  • \(n=2 \rightarrow 3\)
  • \(n=3 \rightarrow 3 - 1 = 2\)
  • \(n=4 \rightarrow 2 - 3 = -1\)
  • \(n=5 \rightarrow -1 - 2 = -3\)
  • \(n=6 \rightarrow -3 - (-1) = -2\)

  • \(n=7 \rightarrow -2 - (-3) = 1\) (Back to start!)

  • Observe Pattern: The sequence repeats every 6 steps: \(1, 3, 2, -1, -3, -2\). We need to find \(100 \pmod 6\). \(100 \div 6 = 16\) with a remainder of \(4\).

  • Final Answer: Since the remainder is 4, \(g(100)\) is the same as the 4th term. \(g(100) = g(4) = \mathbf{-1}\)

Task 3: The "Constant" Trap (McCarthy 91)

Problem Statement:

Define a function \(M(n)\) acting on integers:

  • If \(n > 100\), \(M(n) = n - 10\)
  • If \(n \le 100\), \(M(n) = M(M(n + 11))\)

Goal: Find \(M(99)\).

Solution: This looks like infinite recursion, but it forces a specific value. Let's trace \(M(99)\).

Trace:

  • \(M(99) \to M(M(110))\)
  • Inner \(M(110)\) triggers first rule (\(110 > 100\)) \(\to 100\).
  • Now we have \(M(100) \to M(M(111))\).
  • Inner \(M(111) \to 101\).

  • Now we have \(M(101) \to 91\).

  • Observe Pattern: The function is designed to map every integer \(n \le 100\) to exactly 91.

Final Answer: \(M(99) = \mathbf{91}\)

Task 4: The "Exploding Product" (Fibonacci Connection)

Problem Statement:

Define a function \(h(n)\) recursively by:

  • \(h(0) = 2\)
  • \(h(1) = 2\)
  • \(h(n) = h(n-1) \times h(n-2)\) (for \(n > 1\))

Goal: Express \(h(n)\) in terms of \(n\).

  1. Calculate Base States:

    • \(n=0 \rightarrow 2\)
    • \(n=1 \rightarrow 2\)
    • \(n=2 \rightarrow 2 \times 2 = 4\)
    • \(n=3 \rightarrow 4 \times 2 = 8\)
    • \(n=4 \rightarrow 8 \times 4 = 32\)
    • \(n=5 \rightarrow 32 \times 8 = 256\)

  2. Observe Pattern (Look at Exponents): Rewrite as powers of 2:

    • \(2^1, 2^1, 2^2, 2^3, 2^5, 2^8 \dots\)

The exponents are \(1, 1, 2, 3, 5, 8 \dots\) This is the Fibonacci Sequence!

  1. Derive Formula: Roughly, \(h(n) = 2^{Fib(n)}\).

9. 📝 Check Your Understanding

Ready to test your knowledge on Logical Recursion? 👉 Take the Logical Recursion Quiz