Recursion in Data Structures: Recursive Function

Recursion is a programming technique where a function calls itself to solve a problem. In data structures, recursion is widely used for traversing trees, performing depth‑first search, and solving divide‑and‑conquer problems like sorting and searching.

Components of a Recursive Function

A well‑defined recursive function consists of two essential parts:

• Base Case: The condition that stops the recursion. Without a base case, the function will call itself indefinitely (stack overflow).
• Recursive Case: The part where the function calls itself with modified parameters, gradually moving toward the base case.

Structure of a Recursive Function

def recursive_function(parameters):
    # Base case — stop condition
    if base_condition:
        return base_value

    # Recursive case — function calls itself
    return recursive_function(modified_parameters)

How Recursion Works (Call Stack)

When a recursive function is called, each call is pushed onto the call stack. When the base case is reached, the function begins returning, and each call is popped from the stack. This is why recursion uses O(n) space for the call stack.

factorial(4)
    -> factorial(3)
        -> factorial(2)
            -> factorial(1)
                -> factorial(0)  # Base case: returns 1
            <- returns 1 * 1 = 1
        <- returns 2 * 1 = 2
    <- returns 3 * 2 = 6
<- returns 4 * 6 = 24

Common Recursive Examples

1. Factorial

def factorial(n):
    if n <= 1:
        return 1  # Base case
    return n * factorial(n - 1)  # Recursive case

print(factorial(5))  # Output: 120

2. Fibonacci Sequence

def fibonacci(n):
    if n <= 1:
        return n  # Base case
    return fibonacci(n - 1) + fibonacci(n - 2)  # Recursive case

print(fibonacci(6))  # Output: 8

3. Binary Search (Recursive)

def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1  # Base case: not found
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid  # Base case: found
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)

arr = [1, 3, 5, 7, 9, 11]
print(binary_search_recursive(arr, 7, 0, len(arr) - 1))  # Output: 3

4. Tower of Hanoi

def tower_of_hanoi(n, source, auxiliary, destination):
    if n == 0:
        return  # Base case
    tower_of_hanoi(n - 1, source, destination, auxiliary)
    print(f"Move disk {n} from {source} to {destination}")
    tower_of_hanoi(n - 1, auxiliary, source, destination)

tower_of_hanoi(3, 'A', 'B', 'C')
# Output:
# Move disk 1 from A to C
# Move disk 2 from A to B
# Move disk 1 from C to B
# Move disk 3 from A to C
# Move disk 1 from B to A
# Move disk 2 from B to C
# Move disk 1 from A to C

5. Tree Traversal (In-order)

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def inorder(node, result=None):
    if result is None:
        result = []
    if node:
        inorder(node.left, result)
        result.append(node.val)
        inorder(node.right, result)
    return result

# Example tree:   1
#               /   \
#              2     3
#             / \
#            4   5
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print(inorder(root))  # Output: [4, 2, 5, 1, 3]

Types of Recursion

• Direct Recursion: A function calls itself directly.
• Indirect Recursion: Function A calls function B, which calls function A.
• Tail Recursion: The recursive call is the last operation in the function.
• Non-Tail Recursion: The recursive call is not the last operation.
• Linear Recursion: Each function call makes at most one recursive call.
• Tree Recursion: Each function call makes multiple recursive calls (e.g., Fibonacci).

Complexity Analysis

Recursion vs Iteration

Advantages & Disadvantages

Advantages

• Elegant: Makes code simpler and easier to read for problems with recursive structure.
• Natural: Many problems (trees, graphs, divide‑and‑conquer) are inherently recursive.
• Divide‑and‑Conquer: Enables solving complex problems by breaking them into smaller subproblems.

Disadvantages

• Performance: Function call overhead can make recursion slower than iteration.
• Memory: Each call adds a frame to the stack, which can lead to stack overflow.
• Debugging: Recursive code can be harder to debug and trace.

Applications of Recursion in Data Structures

• Tree Traversal: Preorder, inorder, postorder, and level‑order traversals.
• Graph Traversal: Depth‑First Search (DFS) and Depth‑First Search.
• Sorting Algorithms: Merge Sort, Quick Sort.
• Searching Algorithms: Binary Search (recursive).
• Divide‑and‑Conquer: Problems like maximum subarray, matrix multiplication.
• Dynamic Programming: Memoized recursive solutions for optimization problems.
• Backtracking: N‑Queens, Sudoku solvers, maze solving.
• Parsing: Recursive descent parsers for languages and compilers.

Key Takeaways

• Recursion is a powerful technique where a function calls itself to solve a problem.
• Every recursive function needs a base case to stop recursion and a recursive case that moves toward the base case.
• Recursion uses the call stack and can cause stack overflow if not carefully designed.
• It is ideal for problems with a recursive structure (trees, graphs, divide‑and‑conquer).
• In many cases, recursion can be converted to iteration for better performance.