📘 Module 6: Recursion – Functions Calling Themselves

Goal: Solve problems by breaking them into smaller, identical subproblems. A recursive function has a base case (stops) and a recursive step (calls itself).

🔹 Classic Example: Factorial (n!)

#include <stdio.h>

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

int main() {
    printf("%d\n", factorial(5)); // 120
    return 0;
}

🔹 Another Example: Fibonacci

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

✏️ Exercise 1 (easy)

Write a recursive function int sum(int n) that returns the sum of all integers from 1 to n. Example: sum(5) = 15.

Solution

int sum(int n) {
    if (n == 0) return 0;
    return n + sum(n-1);
}

✏️ Exercise 2 (medium)

Write a recursive function int power(int base, int exp) that computes base^exp (exp ≥ 0). Do NOT use loops.

Solution

int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

✏️ Exercise 3 (practice)

Write a recursive function to print all numbers from 1 to n (in increasing order). Hint: print before or after the recursive call?

Solution

void printUpTo(int n) {
    if (n == 0) return;
    printUpTo(n-1);
    printf("%d ", n);
}
// For n=3: prints "1 2 3"

← Back to Module 5 - Functions Next: Module 7 - Pointers – Direct Memory Access →