Recursion

Definition

• Recursion: a function that calls itself, directly or indirectly, to solve a problem by breaking it into smaller instances of the same problem

Two Essential Components (without which recursion never terminates)

1. Base case — the simplest instance, solved directly without further recursive calls (stops the recursion)
2. Recursive case — breaks the problem down and calls itself on a smaller/simpler input, moving toward the base case

Classic Example — Factorial

FACTORIAL(n):
  IF n == 0: RETURN 1          // base case
  ELSE: RETURN n * FACTORIAL(n-1)  // recursive case

How It Works Internally

• Each call is pushed onto the call stack with its own local variables/parameters; when the base case returns, the stack unwinds, resolving each pending multiplication/operation in reverse order

Recursion vs Iteration

Types

• Direct recursion: function calls itself
• Indirect/mutual recursion: function A calls B, which calls A
• Tail recursion: recursive call is the last operation — some compilers optimize this into iteration (tail-call optimization)

Exam Angle

Every recursive algorithm question expects you to identify the base case and recursive case explicitly — missing the base case is the #1 marked error. Recursion underlies Merge Sort, Quick Sort, Tree traversals, and Backtracking — always mention this cross-linkage.

Solving Recurrences: The Substitution Method (General Theory)

A recurrence relation defines a function in terms of its own smaller input(s) — T(n) in terms of T(n-1), T(n/2), etc. — because a recursive algorithm's running time can only naturally be expressed that way. The substitution method (also called iterative substitution, or "unrolling") solves a recurrence by expanding it step by step until a pattern in terms of the substitution count k emerges, then finding k from the base case and substituting back.

Method — 4 steps:

1. Write the recurrence, then expand the recursive term (T(n-1), T(n/2), etc.) using the recurrence's own definition, one substitution at a time.
2. Spot the pattern — after 2–3 substitutions, write the general expression in terms of k (the number of substitutions done so far).
3. Find k from the base case — set the recursive argument equal to the base case's input value and solve for k.
4. Substitute k back, plug in the base case's actual value, and simplify to get the closed-form solution / Big-O class.

Worked Example: Factorial Recurrence (subtraction-based)

Q: Solve the following recurrence using the substitution method:

$$T(n) = \begin{cases} 1 & n = 1 \\ n \cdot T(n-1) & n > 1 \end{cases}$$

Step 1 — write the original equation and substitute repeatedly:

$$\begin{aligned} T(n) &= n \cdot T(n-1) \\ &= n(n-1) \cdot T(n-2) \\ &= n(n-1)(n-2) \cdot T(n-3) \end{aligned}$$

Step 2 — spot the pattern after k substitutions:

General form:

$$T(n) = \big[n(n-1)(n-2)\cdots(n-k+1)\big] \cdot T(n-k)$$

Step 3 — find k using the base case: recursion stops when the argument hits n = 1:

$$n - k = 1 \implies k = n - 1$$

Step 4 — substitute k = n-1 back in:

$$T(n) = n(n-1)(n-2)\cdots 2 \cdot T(1)$$

Since T(1) = 1:

$$T(n) = n(n-1)(n-2)\cdots 2\cdot 1 = n!$$

Conclusion: $T(n) = n!$ — this recurrence describes exactly the factorial function, so its closed-form solution is $\Theta(n!)$, one of the fastest-growing complexity classes you'll meet — it grows even faster than any fixed exponential $c^n$, since n! keeps multiplying by a growing factor at every step rather than a fixed base.

Key reasoning point: contrast this with the Binary Search recurrence $T(n) = 4 + T(n/2)$ solved below — there, the argument shrinks by division (n/2) each step, giving $k = \log_2 n$ and a fast $O(\log n)$ result; here, the argument shrinks by subtraction (n-1) each step, requiring $k=n-1$ substitutions and multiplying an extra factor at every one of them, giving the enormous $\Theta(n!)$ result. Whether a recurrence divides or subtracts at each step is the single biggest factor separating a fast algorithm from a devastatingly slow one.

Exam angle: FPSC substitution-method questions give you either a division-based recurrence (divide-and-conquer algorithms — Binary Search, Merge Sort: $T(n) = aT(n/b) + f(n)$) or a subtraction-based one (linear recursion — factorial, linear recursive search: $T(n) = T(n-1) + f(n)$). Identify which type you have first — it tells you immediately whether the answer lands in the "fast" family (log n, n log n) or the "slow" family (n!, exponential) before you even finish the algebra.

For the full method catalog — Recursion Tree method, Master Theorem (with its 3 cases and when it doesn't apply), the Characteristic Equation method for Fibonacci-style recurrences, plus a third worked substitution example (T(n) = T(n-1) + log n) and a set of FPSC-pattern practice questions — see Recurrence Relations.

📌 Sample & Repeated FPSC Questions (2016–2026)

📝 Exam Practice: Three Conditions of Recursion

2021, Paper I, Q6(c) (6 marks) — What is recursion in data structures? Explain three conditions of a recursive function with the help of an example.

Model answer: Recursion is a technique where a function solves a problem by calling itself on smaller instance(s) of the same problem until it becomes trivial to solve directly. Three essential conditions:

1. Base case — a condition where the function returns directly without a further recursive call; stops the recursion.
2. Recursive case — the function calls itself with a modified (smaller/simpler) input, working toward the base case.
3. Progress toward termination — every call must move strictly closer to the base case (e.g. a strictly decreasing parameter), guaranteeing eventual termination rather than infinite recursion.

int factorial(int n) {
    if (n == 0) return 1;          // base case
    return n * factorial(n - 1);   // recursive case, n decreases (progress)
}

Key reasoning points: this page's own factorial example already shows condition 1 and 2 — the exam-worthy addition is condition 3 (progress toward termination), which is what actually distinguishes a correct recursive function from one with a syntactically fine base case that the recursive calls never actually reach (e.g. n = n instead of n - 1).

📝 Exam Practice: Base Case (MCQ)

2026, Paper I, Q13 (1 mark) — In Recursion, what is crucial to prevent infinite loops?

• A. Base case ✓
• B. Recursive call
• C. Loop usage
• D. None of these

MCQ Trap: a straightforward drill, but a reminder that FPSC treats "missing/incorrect base case" as the single most-tested recursion failure mode across both MCQ and subjective questions.

📝 Exam Practice: Recursive Power Function

2022, Paper I, Q6(a) (8 marks) — Complete the following recursive function using C++ to calculate k raised to the power n, i.e., k^n. Use of any built-in (library) function is not allowed.

int power(int k, int n)
{
  // write your code here
}

Model answer:

int power(int k, int n)
{
    if (n == 0)          // base case: k^0 = 1
        return 1;
    return k * power(k, n - 1);   // recursive case
}

power(2, 5) computes 2 * power(2,4) = 2 * (2 * power(2,3)) = ... = 32, unwinding 5 levels deep down to power(2,0) = 1.

📝 Exam Practice: Solving a Recurrence — Iterative Substitution (Binary Search)

2016, Paper I, Q5(b) (6 marks) — Find the time complexity of Binary Search by resolving the recurrence $T(1) = 2$ ($n \leq 1$), $T(n) = 4 + T(n/2)$ ($n > 1$), using the iterative substitution method.

Method: repeatedly substitute the recurrence into itself, watching for the pattern after k substitutions, then solve for k using the base case.

Steps 1–4 — substitute repeatedly:

$$\begin{aligned} T(n) &= 4 + T(n/2) \\ &= 4 + \big[4 + T(n/4)\big] = 2(4) + T(n/4) \\ &= 2(4) + \big[4 + T(n/8)\big] = 3(4) + T(n/8) \\ &= 3(4) + \big[4 + T(n/16)\big] = 4(4) + T(n/16) \end{aligned}$$

Step 5 — Spot the pattern across substitutions:

General form after k substitutions:

$$T(n) = k(4) + T(n/2^k)$$

Step 6 — Find k using the base case: recursion stops when the argument hits n = 1:

$$n/2^k = 1 \implies n = 2^k \implies k = \log_2 n$$

Step 7 — Substitute k = log₂n back in:

$$T(n) = 4\log_2 n + T\big(n/2^{\log_2 n}\big) = 4\log_2 n + T(1)$$

Step 8 — Plug in the base case value (T(1) = 2):

$$T(n) = 4\log_2 n + 2$$

Step 9 — Drop constants/lower-order terms for Big-O (the +2 doesn't affect growth as n → ∞):

$$T(n) = O(\log n)$$

Key reasoning points:

• This is the Iteration/Substitution Method — repeatedly expand T(n) until a clear k-dependent pattern emerges, then find k from when the argument reaches the base case ($n/2^k = 1$ here).
• Confirms Binary Search's $O(\log n)$ behavior directly from its recurrence: each comparison halves the search space (the $T(n/2)$ term), so the number of halvings to reach 1 element is $\log_2 n$.
• Also documented on the Asymptotic Notations page (same question, in the context of growth-rate classification) — cross-link the two if this comes up as either a "solve the recurrence" or "find the complexity class" question.

📝 Exam Practice: Exponential Recursion (Fibonacci)

2025, Paper I, Q6(b) (6 marks) — Give pseudocode of implementing Fibonacci sequence recursively. Find the time complexity of this approach and explain how it is calculated.

Model answer:

Function Fibonacci(n):
    if n <= 1: return n
    else: return Fibonacci(n-1) + Fibonacci(n-2)

Time complexity: $O(2^n)$ — each call to Fibonacci(n) (n>1) spawns two further calls, forming a binary recursion tree. The call-count recurrence $T(n) = T(n-1) + T(n-2) + O(1)$ mirrors the Fibonacci recurrence itself, and its solution grows as $O(\varphi^n)$ ($\varphi \approx 1.618$), commonly bounded/quoted as $O(2^n)$.

Exam angle: the blow-up happens because identical subproblems (e.g. Fibonacci(n-3)) are recomputed many times across different branches instead of being cached — an ideal segue if the question also asks for an improvement: memoization or an iterative/DP approach brings this down to O(n).

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2021 · Paper-I · Q6(c) · 6 marks

Q. What is recursion in data structures? Explain three conditions of a recursive function with an example.

Ans.

• Recursion means a function solves a problem by calling itself on a smaller version of the same problem.
• Three conditions:
  • Base case: a simple case solved directly, which stops the recursion.
  • Recursive case: the function calls itself with a smaller or simpler input.
  • Progress toward the base case: every call must move closer to it, otherwise it never ends.

int factorial(int n) {
    if (n <= 1) return 1;            // base case
    return n * factorial(n - 1);     // recursive call on a smaller n
}

• Recursion uses the call stack, so very deep recursion can overflow it.

2025 · Paper-I · Q6(b) · 6 marks

Q. Give pseudocode of the Fibonacci sequence implemented recursively. Find its time complexity and explain how it is calculated.

Ans.

fib(n):
    if n <= 1: return n
    return fib(n - 1) + fib(n - 2)

• Recurrence: T(n) = T(n−1) + T(n−2) + c, with T(0) = T(1) = constant.
• Recursion tree: every call spawns two calls, and the tree has about 2ⁿ nodes, so the time is O(2ⁿ). The tight bound is Θ(φⁿ), where φ ≈ 1.618.
• Why it is slow: the same sub-problems (such as fib(2)) are recomputed many times.
• Improvement: memoization or a loop reduces the time to O(n).

MCQs

2026 P-I · Q13. In recursion, what is crucial to prevent infinite loops?

• (A) Base case ✅
• (B) Recursive call
• (C) Loop usage
• (D) None of these
• Answer: (A) Base case.
• Why: the base case is the condition where the function stops calling itself. Without it (or if the calls never reach it) the recursion never ends and the stack overflows. The recursive call is what repeats, and loops are not needed in recursion.