C Recursion

Recursion Components

if (n <= 0) {
    return 1;  // Stop here
}

return n * factorial(n-1);
// Calls itself

// 5! = 5 * 4!
// 4! = 4 * 3!
// 3! = 3 * 2!

// Stack grows with each call
// Returns when base case hit

🔹 Classic Example: Factorial

Factorial demonstrates recursion perfectly through mathematical calculation. Factorial (represented as n!) multiplies a number by all positive integers below it. For example, 5! equals 5 × 4 × 3 × 2 × 1 = 120. This concept is fundamental in combinatorics, probability, and mathematical computation. Recursion allows us to solve factorial problems elegantly by breaking them into smaller, identical subproblems until reaching the base case.

#include <stdio.h>

int factorial(int n) {
    // Base case: factorial of 0 or 1 is 1
    if (n <= 1) {
        return 1;
    }
    // Recursive case: n! = n × (n-1)!
    else {
        return n * factorial(n - 1);
    }
}

int main() {
    int num = 5;
    int result = factorial(num);
    printf("Factorial of %d is %d\n", num, result);
    
    // Show step by step
    printf("\nStep by step:\n");
    printf("5! = 5 × 4!\n");
    printf("4! = 4 × 3!\n");
    printf("3! = 3 × 2!\n");
    printf("2! = 2 × 1!\n");
    printf("1! = 1 (base case)\n");
    
    return 0;
}

🔹 Fibonacci Sequence

The Fibonacci sequence is another powerful recursion example where each number is the sum of the previous two. This sequence (0, 1, 1, 2, 3, 5, 8, 13, 21, 34...) appears frequently in nature, mathematics, and computer science algorithms. Understanding Fibonacci recursion helps you grasp how recursive functions work by solving the same problem at smaller scales. The sequence demonstrates both the elegance and performance considerations of recursive programming approaches.

#include <stdio.h>

int fibonacci(int n) {
    // Base cases
    if (n <= 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    // Recursive case: F(n) = F(n-1) + F(n-2)
    else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    printf("Fibonacci sequence (first 10 numbers):\n");
    for (int i = 0; i < 10; i++) {
        printf("F(%d) = %d\n", i, fibonacci(i));
    }
    return 0;
}

🔹 Sum of Numbers

Calculate the sum of numbers from 1 to n efficiently using recursive functions. Instead of using loops, recursion breaks down the problem by adding the current number to the sum of all previous numbers. For instance, summing 1 to 5 yields 5 + 4 + 3 + 2 + 1 = 15. This approach teaches how recursion simplifies complex problems and develops better problem-solving skills for mathematical computations in programming.

#include <stdio.h>

int sumNumbers(int n) {
    // Base case
    if (n <= 0) {
        return 0;
    }
    // Recursive case: sum(n) = n + sum(n-1)
    else {
        return n + sumNumbers(n - 1);
    }
}

void printSum(int n) {
    if (n <= 0) {
        printf("0");
    } else {
        printf("%d", n);
        if (n > 1) {
            printf(" + ");
            printSum(n - 1);
        }
    }
}

int main() {
    int num = 5;
    printf("Sum from 1 to %d:\n", num);
    printSum(num);
    printf(" = %d\n", sumNumbers(num));
    return 0;
}

🔹 Power Function

The power function calculates x raised to the power n using recursive multiplication. Rather than using built-in functions, recursive implementation multiplies the base number by itself repeatedly. For example, 2⁴ equals 2 × 2 × 2 × 2 = 16. Understanding recursive power functions enhances your knowledge of exponentiation and demonstrates how recursion replaces iterative approaches effectively in mathematical operations.

#include <stdio.h>

int power(int base, int exp) {
    // Base case: any number to power 0 is 1
    if (exp == 0) {
        return 1;
    }
    // Recursive case: base^exp = base × base^(exp-1)
    else {
        return base * power(base, exp - 1);
    }
}

int main() {
    int base = 2, exponent = 4;
    int result = power(base, exponent);
    
    printf("%d^%d = %d\n", base, exponent, result);
    printf("Calculation: %d × %d × %d × %d = %d\n", 
           base, base, base, base, result);
    return 0;
}

🔹 Recursion Tips

Master recursion by following essential best practices and guidelines. Always define a clear base case to stop recursion and prevent infinite loops. Ensure each recursive call moves toward the base case and breaks the problem into smaller, manageable subproblems. Use recursion for problems naturally suited to it, like tree traversal and factorial calculation. Understanding these principles transforms recursion from confusing into powerful programming technique.