Recursion

Introduction

Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem. It’s a powerful method for solving problems that can be broken down into similar sub-problems. Recursive solutions often provide elegant and intuitive code for problems involving mathematical sequences, tree structures, and divide-and-conquer algorithms.

Key Concepts

Base Case: Condition that stops the recursive calls Recursive Case: Function calling itself with modified parameters Call Stack: Memory structure that manages recursive function calls Stack Overflow: Error when recursion depth exceeds memory limits Tail Recursion: Recursive call as the last operation in function

Basic Recursive Structure

Essential Components

returnType recursiveFunction(parameters) {
    // Base case - stops recursion
    if (baseCondition) {
        return baseValue;
    }
    
    // Recursive case - function calls itself
    return recursiveFunction(modifiedParameters);
}

Simple Example: Factorial

#include <stdio.h>

int factorial(int n) {
    // Base case
    if (n <= 1) {
        return 1;
    }
    
    // Recursive case
    return n * factorial(n - 1);
}

int main() {
    int num = 5;
    printf("Factorial of %d = %d\n", num, factorial(num));
    return 0;
}

Mathematical Recursion Examples

Fibonacci Series

#include <stdio.h>

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

void printFibonacci(int terms) {
    printf("Fibonacci series: ");
    for (int i = 0; i < terms; i++) {
        printf("%d ", fibonacci(i));
    }
    printf("\n");
}

int main() {
    printFibonacci(10);
    return 0;
}

Power Function

#include <stdio.h>

int power(int base, int exponent) {
    // Base case
    if (exponent == 0) {
        return 1;
    }
    
    // Recursive case
    return base * power(base, exponent - 1);
}

int main() {
    printf("2^5 = %d\n", power(2, 5));
    printf("3^4 = %d\n", power(3, 4));
    return 0;
}

Array and String Recursion

Sum of Array Elements

#include <stdio.h>

int arraySum(int arr[], int size) {
    // Base case
    if (size <= 0) {
        return 0;
    }
    
    // Recursive case
    return arr[size - 1] + arraySum(arr, size - 1);
}

int main() {
    int numbers[] = {1, 2, 3, 4, 5};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    
    printf("Sum of array elements: %d\n", arraySum(numbers, size));
    return 0;
}

String Length and Reversal

#include <stdio.h>

int stringLength(char *str) {
    if (*str == '\0') {
        return 0;
    }
    return 1 + stringLength(str + 1);
}

void printReverse(char *str) {
    if (*str == '\0') {
        return;
    }
    printReverse(str + 1);
    printf("%c", *str);
}

int main() {
    char text[] = "Hello";
    
    printf("String: %s\n", text);
    printf("Length: %d\n", stringLength(text));
    printf("Reversed: ");
    printReverse(text);
    printf("\n");
    
    return 0;
}

Advanced Recursive Algorithms

Binary Search

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int target) {
    if (left > right) {
        return -1;  // Element not found
    }
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] > target) {
        return binarySearch(arr, left, mid - 1, target);
    } else {
        return binarySearch(arr, mid + 1, right, target);
    }
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 23;
    
    int result = binarySearch(arr, 0, size - 1, target);
    
    if (result != -1) {
        printf("Element %d found at index %d\n", target, result);
    } else {
        printf("Element %d not found\n", target);
    }
    
    return 0;
}

Tower of Hanoi

#include <stdio.h>

void hanoi(int n, char source, char destination, char auxiliary) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", source, destination);
        return;
    }
    
    hanoi(n - 1, source, auxiliary, destination);
    printf("Move disk %d from %c to %c\n", n, source, destination);
    hanoi(n - 1, auxiliary, destination, source);
}

int main() {
    int disks = 3;
    printf("Solution for Tower of Hanoi with %d disks:\n", disks);
    hanoi(disks, 'A', 'C', 'B');
    return 0;
}

Recursion vs Iteration

Recursive vs Iterative Factorial

#include <stdio.h>

// Recursive version
int factorialRecursive(int n) {
    if (n <= 1) return 1;
    return n * factorialRecursive(n - 1);
}

// Iterative version
int factorialIterative(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

int main() {
    int num = 6;
    
    printf("Recursive factorial of %d: %d\n", 
           num, factorialRecursive(num));
    printf("Iterative factorial of %d: %d\n", 
           num, factorialIterative(num));
    
    return 0;
}

Tail Recursion

Tail Recursive Factorial

#include <stdio.h>

int factorialTail(int n, int accumulator) {
    if (n <= 1) {
        return accumulator;
    }
    return factorialTail(n - 1, n * accumulator);
}

int factorial(int n) {
    return factorialTail(n, 1);
}

int main() {
    printf("Tail recursive factorial of 5: %d\n", factorial(5));
    return 0;
}

Recursion with Multiple Base Cases

Greatest Common Divisor (GCD)

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    int num1 = 48, num2 = 18;
    printf("GCD of %d and %d: %d\n", num1, num2, gcd(num1, num2));
    return 0;
}

Debugging Recursive Functions

Trace Recursive Calls

#include <stdio.h>

int fibonacci_debug(int n, int depth) {
    // Print indentation based on recursion depth
    for (int i = 0; i < depth; i++) {
        printf("  ");
    }
    printf("fibonacci(%d) called\n", n);
    
    if (n <= 1) {
        for (int i = 0; i < depth; i++) {
            printf("  ");
        }
        printf("fibonacci(%d) returns %d\n", n, n);
        return n;
    }
    
    int result = fibonacci_debug(n - 1, depth + 1) + 
                 fibonacci_debug(n - 2, depth + 1);
    
    for (int i = 0; i < depth; i++) {
        printf("  ");
    }
    printf("fibonacci(%d) returns %d\n", n, result);
    
    return result;
}

int main() {
    printf("Tracing fibonacci(4):\n");
    fibonacci_debug(4, 0);
    return 0;
}

Common Recursion Patterns

Tree Traversal Structure

void processNode(Node* node) {
    if (node == NULL) {
        return;  // Base case
    }
    
    // Process current node
    printf("%d ", node->data);
    
    // Recursive calls for subtrees
    processNode(node->left);
    processNode(node->right);
}

Divide and Conquer Pattern

resultType divideAndConquer(problemType problem) {
    if (isBaseCase(problem)) {
        return solveDirectly(problem);
    }
    
    subProblemType* subProblems = divide(problem);
    resultType* subResults = malloc(sizeof(resultType) * numSubProblems);
    
    for (int i = 0; i < numSubProblems; i++) {
        subResults[i] = divideAndConquer(subProblems[i]);
    }
    
    return combine(subResults);
}

Best Practices and Guidelines

Design Principles:

1. Always define base case to prevent infinite recursion
2. Ensure progress toward base case in each recursive call
3. Consider iterative alternatives for simple problems
4. Use recursion for naturally recursive problems (trees, fractals)
5. Be aware of stack overflow for deep recursion

When to Use Recursion:

• Problems with recursive structure (trees, graphs)
• Mathematical sequences and series
• Divide and conquer algorithms
• Backtracking problems
• When solution mirrors problem structure

When to Avoid Recursion:

• Simple iterative problems
• Performance-critical code with deep recursion
• Limited stack space environments
• Problems with overlapping subproblems (use dynamic programming)

Summary

Recursion is a powerful programming technique that breaks complex problems into smaller, similar sub-problems. It requires a base case to stop recursion and a recursive case that progresses toward the base case. While elegant for many problems, recursion can be memory-intensive and slower than iterative solutions. Understanding when and how to use recursion effectively is crucial for solving complex algorithmic problems and working with recursive data structures.

Part of BCA Programming with C Course (UGCOA22J201)