Recursion in C Language

 

Introduction to Recursion

Let's make recursion super easy to understand. Don't worry — we'll take it slow, with real code, real examples, and real results.

🔄 What is Recursion?

📘 Simple Definition

Recursion is when a function calls itself to solve a smaller version of the same problem.

🧠 Everyday Example

Think of looking into a mirror that reflects another mirror—you keep seeing the same image repeating. That's like recursion!

⚙️ How Recursion Works in C

In recursion, a function:

1. Calls itself again and again
2. Stops when a certain condition is met (called base case)

📌 Two Main Parts of Recursion

• Base Case – when to stop calling the function
• Recursive Case – when to call the function again

💡 Why Use Recursion?

📈 When Is It Useful?

• When a problem can be broken into smaller parts
• Great for tasks like:
  • Calculating factorials
  • Printing Fibonacci numbers
  • Tree or file directory structures

🧾 Basic Syntax of a Recursive Function

return_type function_name(parameters) {
    if (base_condition)
        return value;
    else
        return function_name(smaller_problem);
}

🔢 Example 1: Factorial of a Number

📘 What is Factorial?

Factorial of 5 (written as 5!) = 5 × 4 × 3 × 2 × 1 = 120

📌 Code Example:

#include <stdio.h>

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

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

💡 Output:

Factorial of 5 is 120

🧠 How It Works:

• factorial(5) → 5 * factorial(4)
• factorial(4) → 4 * factorial(3)
• …
• factorial(0) → 1 (base case)
• Then it returns back up the chain.

🔁 Example 2: Fibonacci Series

📘 What is Fibonacci?

Series: 0, 1, 1, 2, 3, 5, 8...
Each number = sum of previous two numbers.

📌 Code Example:

#include <stdio.h>

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

int main() {
    int n = 6;
    for (int i = 0; i < n; i++) {
        printf("%d ", fibonacci(i));
    }
    return 0;
}

💡 Output:

0 1 1 2 3 5

➕ Example 3: Sum of Natural Numbers

📘 Find sum from 1 to n

📌 Code Example:

#include <stdio.h>

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

int main() {
    int result = sum(5);
    printf("Sum = %d\n", result);
    return 0;
}

💡 Output:

Sum = 15

⚠️ Infinite Recursion (Stack Overflow)

If you forget the base case, your function keeps calling itself forever and crashes.

📌 Dangerous Code:

void loop() {
    printf("Hello\n");
    loop();  // no base case!
}

🚫 What Happens?

• Stack memory gets full
• Program crashes (stack overflow)

⚖️ Recursive vs Iterative

Feature	Recursion	Iteration
Uses Stack	Yes	No
Easier Code	Yes	Sometimes
Faster	No	Usually
Memory Use	More	Less

✅ Advantages of Recursion

• Code looks clean
• Great for complex problems
• Easy to break problems down

🚫 Disadvantages

• Slower execution
• High memory use
• Risk of infinite loop

🛡️ Tips for Safe Recursion

• Always write a base case
• Avoid deep recursion if not needed
• Try iteration when recursion is too heavy

🌐 Real-Life Uses of Recursion

• File systems
• Game design (levels, puzzles)
• Math calculations
• Tree traversals in data structures

🧾 Conclusion

Recursion may look scary at first, but it's just a function that calls itself. As long as you include a base case, you're safe!

Use it wisely and it can solve many problems more easily than loops.

❓ FAQs

1. What is recursion in C?
It's when a function calls itself to solve smaller versions of the problem.

2. What is the base case in recursion?
It's the stopping condition to prevent infinite calls.

3. Can recursion be replaced with loops?
Yes, but sometimes recursion makes the code cleaner.

4. Is recursion faster than iteration?
Usually no. Iteration is often faster and uses less memory.

5. What happens without a base case?
Your program crashes due to infinite function calls (stack overflow).