Recursion

Recursion is a method of solving problems where the solution depends on solutions to smaller instances of the same problem. It is characterized by a base case and a recursive case.

Common Recursive Problems

Factorial Calculation: Calculating the factorial of a number.
Fibonacci Sequence: Finding the nth Fibonacci number.
Permutations of a String: Generating all permutations of a string.
Tower of Hanoi: Moving disks from one rod to another using recursion.

Example Code: Factorial Calculation

#include <stdio.h>
int factorial(int n) {
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}

int main() {
    int num = 5; // Change this value for different factorials
    printf("Factorial of %d is %d\n", num, factorial(num));
    return 0;
}

Output

Factorial of 5 is 120

Example Code: Tower of Hanoi

#include <stdio.h>
void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n == 1) {
        printf("Move disk 1 from rod %c to rod %c\n", from_rod, to_rod);
        return;
    }
    towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
    printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
    towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

int main() {
    int n = 3; // Change this value for more disks
    towerOfHanoi(n, 'A', 'C', 'B'); // A, B and C are names of rods
    return 0;
}

Output

Move disk 1 from rod A to rod C Move disk 2 from rod A to rod B Move disk 1 from rod C to rod B Move disk 3 from rod A to rod C Move disk 1 from rod B to rod A Move disk 2 from rod B to rod C Move disk 1 from rod A to rod C