Recursive relation

Overview

A recursive relation is how a function expresses a problem in terms of a strictly smaller version of that exact same problem.

It allows complex problems to be broken down into identical, simpler subproblems. By taking a 'leap of faith'—assuming the recursive call correctly solves the smaller case—you only need to figure out how to combine that result with the current step.

Where used: Processing nested JSON objects where a value can be another JSON object., Traversing a file system directory tree where a folder can contain other folders.

Why learn this

• Defining the recursive relation is the core logic of any recursive algorithm.
• It teaches you the 'leap of faith' approach to problem solving: assume the subproblem is already solved and focus on the current step.
• Many algorithm complexities are defined by how their recursive relation shrinks the input size. For example, Merge Sort splits an array in half (two T(n/2) subproblems) and takes O(n) work to combine them, resulting in an O(n log n) runtime.

Aha moment

def fibonacci(n):
    if n <= 1:
        return n
    # The leap of faith: assume fibonacci(n-1) and fibonacci(n-2) work
    return fibonacci(n - 1) + fibonacci(n - 2)

Prediction: The result is calculated by blindly trusting that the smaller recursive calls return the correct sequence values.

Common guess: You have to mentally trace down all the branches to understand how it works.

Tracing the entire execution tree is exhausting and error-prone. The 'leap of faith' means you only need to verify the base cases and that the recursive relation correctly combines the results of the strictly smaller subproblems.

Common mistakes

• Restating the exact same problem: Passing the exact same input to the recursive call means no progress is made. The recursive call must operate on a STRICTLY SMALLER subproblem to eventually reach the base case.
• Failing to combine the result: A recursive call computes the answer for the smaller subproblem. You must remember to take its return value and combine it with the current step's data to produce the final answer for the current level.

Recall questions

• What is the 'leap of faith' in recursive thinking?
• Why must the input to a recursive call be strictly smaller than the current input?
• If a problem is split into two halves and takes O(n) work to combine them, what classic algorithm does its recursive relation describe?

Understanding checks

In the fast exponentiation algorithm to compute `Pow(x, n)`, why is the recursive relation for even `n` defined as `(x^(n/2))^2` instead of `x * Pow(x, n - 1)`?

By halving the exponent `n/2`, the input size shrinks exponentially, turning an O(n) linear operation into an O(log n) operation.

A recursive relation that halves the search space or input size is drastically more efficient than one that merely decrements it.

Consider a function `def sum_array(arr): if not arr: return 0; return arr[0] + sum_array(arr[1:])`. What does the recursive relation here represent?

The sum of the entire array is the first element plus the sum of the strictly smaller sub-array (everything after the first element).

This perfectly illustrates expressing the problem in terms of a smaller version of itself: the sum of N items is 1 item + the sum of N-1 items.

Practice tasks

Write the recursive relation

You are writing a function to reverse a string `s`. The base case is when the string is empty or length 1. Write the recursive relation using a 'leap of faith'—assuming the function can already reverse the strictly smaller substring `s[1:]`.

Continue learning

Previous: Base case

Next: The call stack

Return to DSA Roadmap