Recursion in Data Structures

Recursion is a fundamental concept in computer science where a function solves a problem by calling itself repeatedly. Instead of solving a problem in one step, recursion breaks it down into smaller and simpler subproblems, each of which resembles the original problem. The final solution is obtained by combining the results of these smaller subproblems.

This approach is particularly powerful for problems that show self-similarity, meaning the problem structure repeats itself at smaller scales. Many data structures such as linked lists and trees naturally use recursion because of their hierarchical nature.

• A recursive solution reduces a problem into smaller instances of the same problem.
• Each recursive call works on a simpler version of the input.
• The process continues until a condition is met where no further recursion is needed.

Basic Structure of a Recursive Function

Every recursive function must contain two essential components to work correctly:

Base Case

• This is the condition where recursion stops.
• It prevents infinite recursion.
• It provides a direct answer without further function calls.

Recursive Case

• This is the part where the function calls itself.
• It reduces the problem size in each step.
• It moves the computation toward the base case.

Without a base case, recursion will continue indefinitely and cause a program crash (stack overflow).

Features of Recursion

Recursion has several important characteristics that distinguish it from normal function execution:

Depth of Recursion

• Refers to the number of times a function calls itself before reaching the base case.
• A deeper recursion means more memory usage.

Function Call Stack

• Each recursive call is stored in memory (stack).
• When the base case is reached, the calls are resolved in reverse order.

Local Variables

• Each recursive call has its own set of local variables.
• These variables exist only within that specific function call.

Understanding Recursion with an Example

Consider a recursive function that calculates the sum of numbers from n to 0:

• The function keeps calling itself with n − 1.
• When n = 0, it returns 0 (base case).
• Then results are added as the function returns back step by step.

This process demonstrates how recursion works in two phases:

Forward Phase (Calling) : Function keeps calling itself.

Backward Phase (Returning) : Results are combined as calls return.

Example 1: Factorial (C Code)

The factorial of a number is defined as:

• n! = n × (n−1)!
• 0! = 1

Code Example

#include <stdio.h>
long fact(int n)
{
    if (n <= 1)
        return 1;   // Base case
    return n * fact(n - 1);  // Recursive case
}
int main()
{
    int num = 5;
    printf("Factorial = %ld\n", fact(num));
    return 0;
}

Explanation

• The function keeps calling itself with n − 1.
• When n = 1, recursion stops.
• Then results are multiplied while returning.

Example 2: Sum of Numbers (C Code)

This function calculates the sum from n to 0.

Code Example

#include <stdio.h>
int sum(int n)
{
    if (n == 0)
        return 0;   // Base case
    return n + sum(n - 1);  // Recursive call
}
int main()
{
    int num = 10;
    printf("Sum = %d\n", sum(num));
    return 0;
}

Explanation

• Calls go from 10 → 9 → 8 → ... → 0
• Then results are added during return:
  • sum(1) = 1
  • sum(2) = 2 + 1
  • and so on

Example 3: Pattern Printing (Triangle)

This example demonstrates recursion with output during the return phase.

Code Example

#include <stdio.h>
void triangle(int x)
{
    if (x <= 0)
        return;   // Base case
    triangle(x - 1);  // Recursive call
    for (int i = 1; i <= x; i++)
        printf("*");
    printf("\n");
}
int main()
{
    triangle(5);
    return 0;
}

Explanation

• Function first goes deep until base case.
• Then prints:

*
**
***
****
*****

Trace of Recursion

When tracing a recursive function:

• Calls go deeper until the base case is reached.
• After reaching the base case:
  • Execution returns step-by-step.
  • Each step completes pending operations.

Example flow:

• Call with n = 7
• Calls continue until n = 0 (base case)
• Then results are processed from n=1 up to n = 7

Recursion in Data Structures

Recursion is widely used in data structures because many structures are naturally recursive.

1. Recursion in Linked Lists

A linked list consists of nodes where each node points to the next node. This structure naturally supports recursion.

• The base case occurs when the list is empty.
• The recursive step processes the current node and moves to the next node.

For example, while printing a list:

• Print the current node value.
• Recursively call the function for the next node.

This continues until the end of the list is reached.

Code Example

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *next;
};

void printList(struct node *head)
{
    if (head == NULL)
        return;  // Base case

    printf("%d ", head->data);
    printList(head->next);  // Recursive call
}

Explanation

• Base case: when list is empty
• Recursive step: move to next node

2. Recursion in Binary Trees

Binary trees are inherently recursive structures because each node has:

• A left subtree
• A right subtree

Tree traversal is commonly implemented using recursion.

For example, in inorder traversal:

• Visit the left subtree
• Process the current node
• Visit the right subtree
• The base case occurs when the node is empty.
• Recursion ensures that all nodes are visited in order.

Code Example (Inorder Traversal)

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

void inorder(struct node *root)
{
    if (root == NULL)
        return;  // Base case

    inorder(root->left);      // Left subtree
    printf("%d ", root->data); // Root
    inorder(root->right);     // Right subtree
}

Explanation

• Visit left subtree
• Print node
• Visit right subtree

Advantages of Recursion

Recursion provides several benefits, especially for complex problems:

Simplifies Code

• Makes programs easier to understand.
• Reduces the need for complex loops.

Natural for Hierarchical Problems

• Works well with trees, graphs, and divide-and-conquer algorithms.

Elegant and Concise

• Often shorter and cleaner than iterative solutions.

Useful for Advanced Techniques

• Widely used in:
  • Divide and Conquer
  • Backtracking
  • Tree Traversals

Disadvantages of Recursion

Despite its advantages, recursion also has limitations:

Higher Memory Usage

• Each function call consumes stack memory.
• Deep recursion may cause stack overflow.

Performance Overhead

• Function calls are slower than loops.
• May involve repeated calculations.

Inefficiency in Some Cases

• Example: naive Fibonacci recursion repeats work unnecessarily.

Conclusion

Recursion is a powerful and elegant programming technique that allows problems to be solved by breaking them into smaller subproblems. It is especially useful for problems involving hierarchical or repetitive structures such as trees and linked lists.

It relies on:

• A base case to stop execution
• A recursive case to reduce the problem

While recursion can simplify problem-solving and produce clean code, it must be used carefully to avoid excessive memory usage and performance issues. Understanding when and how to use recursion effectively is an essential skill for designing efficient algorithms.