Recursion; Arrays — 1D, 2D, Multi-dimensional

Recursion

What is Recursion?

A function that calls itself to solve smaller subproblems.

Every recursive function needs:

1. Base case — termination condition (no more recursion)
2. Recursive case — function calls itself with smaller input

// Recursive factorial
long long factorial(int n) {
    if (n == 0 || n == 1) return 1;  // base case
    return n * factorial(n - 1);     // recursive case
}

// How factorial(4) works:
// factorial(4) = 4 * factorial(3)
//              = 4 * 3 * factorial(2)
//              = 4 * 3 * 2 * factorial(1)
//              = 4 * 3 * 2 * 1  = 24

Fibonacci Series

// Recursive Fibonacci
int fibonacci(int n) {
    if (n <= 0) return 0;      // base case 1
    if (n == 1) return 1;      // base case 2
    return fibonacci(n-1) + fibonacci(n-2);  // recursive case
}

// Print N terms
void print_fibonacci(int n) {
    for (int i = 0; i < n; i++) {
printf("%d ", fibonacci(i));
    }
    printf("\n");
}
// print_fibonacci(8) → 0 1 1 2 3 5 8
13

// IMPORTANT: Recursive Fibonacci is SLOW (exponential time O(2^n))
// Iterative version is much faster O(n)

Tower of Hanoi (Classic Recursion)

void tower_of_hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    tower_of_hanoi(n-1, from, aux, to);       // move n-1 disks to aux
    printf("Move disk %d from %c to %c\n", n, from, to);
    tower_of_hanoi(n-1, aux, to, from);       // move n-1 disks from aux to destination
}

// tower_of_hanoi(3, 'A', 'C', 'B');
// 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

Arrays — 1D, 2D, Multi-dimensional

1D Arrays

#include <stdio.h>

// Accepting and printing array elements (as functions per PDF)
void accept_array(int arr[],
int n) {
    printf("Enter %d elements: ", n);
    for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
    }
}

void print_array(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ",
arr[i]);
    }
    printf("\n");
}

void reverse_array(int arr[], int n) {
    int i = 0, j = n - 1;
    while (i < j) {
int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i++;
        j--;
}
}

// Maximum and minimum
void find_max_min(int arr[], int n, int *max, int *min) {
    *max =
*min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > *max) *max = arr[i];
if (arr[i] < *min) *min = arr[i];
    }
}

// Remove duplicates
int remove_duplicates(int arr[], int n) {
    int unique = 0;
    for
(int i = 0; i < n; i++) {
        int found = 0;
        for (int j = 0; j < unique; j++) {
if (arr[i] == arr[j]) { found = 1; break; }
        }
        if (!found) arr[unique++] =
arr[i];
    }
    return unique;   // returns count of unique elements
}

int main() {
    int arr[5] = {56, 4, 43, 33, 2};

    printf("Original: ");
    print_array(arr, 5);           // 56 4 43 33 2

    reverse_array(arr, 5);
    printf("Reversed: ");
    print_array(arr, 5);           // 2 33 43 4 56

    int max, min;
    find_max_min(arr, 5, &max, &min);
    printf("Max=%d, Min=%d\n", max, min);  // Max=56, Min=2

    return 0;
}

2D Arrays (Matrix)

#include <stdio.h>
#define ROWS 3
#define COLS 3

void print_matrix(int mat[][COLS], int rows, int cols) {
    for (int i = 0; i < rows; i++)
{
        for (int j = 0; j < cols; j++) {
            printf("%4d", mat[i][j]);
        }
printf("\n");
    }
}

void matrix_multiply(int a[][COLS], int b[][COLS], int c[][COLS], int n) {
    for (int i =
0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            c[i][j] = 0;
for (int k = 0; k < n; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
}
    }
}

void transpose(int mat[][COLS], int result[][COLS], int n) {
    for (int i = 0; i < n; i++)
{
        for (int j = 0; j < n; j++) {
            result[j][i] = mat[i][j];
        }
}
}

int main() {
    int matrix[3][3] = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    printf("Matrix:\n");
    print_matrix(matrix, 3, 3);
    return 0;
}