C Programming - Beginner to Brilliance / Functions in C

Recursion

🧠 What is Recursion?

Recursion is when a function calls itself to solve a problem.

📖 Simple definition:

“A recursive function is a function that solves a problem by breaking it into smaller sub-problems, and then calls itself to solve those sub-problems.”

It continues doing this until a certain condition is met (called the base case), which stops the recursion.

📦 Real-Life Analogy

🪞 Russian Dolls (Matryoshka Dolls)

Imagine you have a big doll, and inside it is a smaller one, and then a smaller one inside that, and so on.

Opening each doll leads to the next, until the smallest doll — that’s your base case. Then you start closing them in reverse.

🛠️ How Recursion Works Internally?

When a function calls itself:

  1. The current function call pauses.

  2. A new function call is pushed onto the stack.

  3. This continues until the base case is reached.

  4. Then the calls are popped off the stack one by one, finishing each paused call.

🧱 This behavior uses something called the Call Stack.

🧪 Components of a Recursive Function

Every recursive function has two main parts:

  1. Base Case (Stopping Condition)

    ➤ The condition where the recursion stops.

    ➤ Prevents infinite recursion.

  2. Recursive Case

    ➤ The part where the function calls itself to solve a smaller problem.

📌 Syntax of a Recursive Function:

return_type function_name(parameters) {
    if (base_case_condition) {
        return some_value;
    } else {
        return function_name(smaller_problem); // Recursive call
    }
}

💡 Let’s Understand with an Example: Factorial

🧮 Factorial of a number n is:

n! = n × (n - 1) × (n - 2) × ... × 1

So,

5! = 5 × 4 × 3 × 2 × 1 = 120

✅ Factorial using Recursion:

#include <stdio.h>

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

int main() {
    int num = 5;
    printf("Factorial of %d is %d", num, factorial(num));
    return 0;
}
Factorial of 5 is 120

🎯 More Examples of Recursion

The Fibonacci series:

0, 1, 1, 2, 3, 5, 8, ...

Where:

fib(n) = fib(n-1) + fib(n-2)
fib(0) = 0, fib(1) = 1
int fib(int n) {
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fib(n - 1) + fib(n - 2);
}
int power(int x, int n) {
    if (n == 0)
        return 1;
    else
        return x * power(x, n - 1);
}
int sum(int n) {
    if (n == 0)
        return 0;
    else
        return n + sum(n - 1);
}

⚠️ Common Mistakes in Recursion

Mistake

What Happens

❌ No base case

Infinite recursion → stack overflow error

❌ Base case never reached

Stack overflow

❌ Modifying parameters incorrectly

Wrong results

🔁 Recursion vs Loop

Feature

Recursion

Loop

Uses Call Stack

Yes

No

Code Length

Shorter (often)

Longer (often)

Performance

Slower (more memory)

Faster

Complexity

Higher (harder to trace)

Easier to debug

🧠 Pro Tip: Recursion is elegant, but in practice, loops are more efficient for most real-world C programs.

📌 When to Use Recursion

✅ Use recursion when:

  • The problem is naturally recursive (like trees, graphs).

  • You can clearly define a base case and recursive case.

  • Simplicity is more important than performance.

❌ Avoid recursion when:

  • Performance and memory are critical.

  • The depth of recursion could be too large (causing stack overflow).