Recursion Technique in DSA

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.

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

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!