Algorithms

Recursion

Recursive functions and problem-solving techniques.

Recursion Basics

A function that calls itself to solve smaller instances of the same problem.

recursion_basics.c

#include <stdio.h>

// Recursive function needs:
// 1. Base case (stopping condition)
// 2. Recursive case (calls itself)

void countDown(int n) {
    // Base case
    if (n <= 0) {
        printf("Done!\n");
        return;
    }
    
    // Recursive case
    printf("%d\n", n);
    countDown(n - 1);
}

int main() {
    countDown(5);
    return 0;
}

Common Examples

Factorial

factorial.c

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

Fibonacci

fibonacci.c

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

Sum of Array

array_sum.c

int arraySum(int arr[], int n) {
    if (n <= 0)
        return 0;
    return arr[n - 1] + arraySum(arr, n - 1);
}

Tower of Hanoi

hanoi.c

#include <stdio.h>

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

int main() {
    towerOfHanoi(3, 'A', 'B', 'C');
    return 0;
}