Recursion Technique in DSA

What is the Recursion Technique?

Recursion is a technique where a function calls itself to solve a problem. It breaks down a large problem into smaller, more manageable subproblems.

Key Characteristics of Recursion

• Each recursive call works on a smaller instance of the same problem.
• A base case is required to terminate recursion.
• Uses call stack to keep track of function calls.
• Can be implemented as top-down (recursive) or bottom-up (iterative with memoization).

General Recursion Pseudocode

// Recursive function to solve a problem
function recursiveSolve(problem):
    if baseCase(problem):
        return baseResult

    smallerProblem = breakIntoSubproblem(problem)
    result = recursiveSolve(smallerProblem)
    return combine(result)

Explanation of Steps

• baseCase(problem) — Condition where recursion stops (e.g., n == 0).
• baseResult — Direct result when base case is reached (e.g., 1 for factorial of 0).
• breakIntoSubproblem(problem) — Reduce the problem into a simpler version.
• recursiveSolve(smallerProblem) — Self-call to solve the reduced problem.
• combine(result) — Combine current result with recursive result (e.g., multiply, add).

Where is Recursion Used?

• Factorial and Fibonacci problems
• Binary Tree Traversals (Inorder, Preorder, Postorder)
• Divide and Conquer Algorithms (Merge Sort, Quick Sort)
• Dynamic Programming (Top-Down with Memoization)
• Graph DFS Traversal
• Backtracking (uses recursion internally)

Recursion provides a natural and elegant solution to many problems, especially those that can be defined in terms of smaller subproblems. It is essential to ensure a valid base case to avoid infinite recursion and stack overflow.

Example 1: Factorial — Explained for Beginners

Problem Statement:

Find the factorial of a number n, where factorial is defined as:

• 0! = 1
• n! = n × (n - 1) × (n - 2) × ... × 1 for n > 0

For example:

factorial(5) = 5 × 4 × 3 × 2 × 1 = 120

Recursive Approach

This problem can be elegantly solved using recursion because it naturally fits the definition of factorial: n! = n × (n - 1)!

Step-by-step Explanation:

1. Start from factorial(n).
2. If n == 0, return 1 (base case).
3. Otherwise, return n × factorial(n - 1).

Pseudocode

// Recursive factorial
function factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

Why It Works:

This method solves the problem by repeatedly breaking it into smaller subproblems until it reaches the simplest case (0!). The result is built by multiplying the results of the smaller problems.

Time Complexity:

• O(n) — one call per decrement from n to 0.

Space Complexity:

• O(n) — due to the call stack used in recursion.

The recursive factorial problem is a foundational example to understand recursion. It introduces the concepts of base cases, recursive calls, and the call stack. As the problem size increases, understanding stack depth and function return values becomes crucial.

Example 2: Fibonacci Number

Problem Statement:

Find the nth Fibonacci number, where the Fibonacci sequence is defined as:

• F(0) = 0
• F(1) = 1
• F(n) = F(n - 1) + F(n - 2) for n ≥ 2

This means every number in the sequence is the sum of the two previous numbers. Example sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Understanding the Recursive Approach

Recursion is a technique where a function calls itself to solve smaller instances of the same problem. In Fibonacci, we can define the solution recursively because each number depends on the previous two.

Recursive Logic:

1. If n is 0, return 0.
2. If n is 1, return 1.
3. Otherwise, return fib(n - 1) + fib(n - 2).

Pseudocode

// Simple recursive function to find nth Fibonacci number
function fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

Example Execution: fib(4)

fib(4)
= fib(3) + fib(2)
= (fib(2) + fib(1)) + (fib(1) + fib(0))
= ((fib(1) + fib(0)) + 1) + (1 + 0)
= ((1 + 0) + 1) + (1 + 0)
= 2 + 1 = 3

Why It Works:

This recursive solution mirrors the mathematical definition of Fibonacci. It’s intuitive and easy to implement.

Time Complexity:

• O(2ⁿ) — exponential time due to repeated subproblem calls.

Space Complexity:

• O(n) — call stack depth up to n.

Note: While recursion is elegant, it’s not the most efficient way to solve Fibonacci due to overlapping subproblems. But it is a great way to understand how recursion works!