🟡 Intermediate · Lesson 19

Recursion

What is Recursion?

A function that calls itself is called a recursive function, and this technique is called recursion. Every recursive solution has two essential parts:

Base Case — The condition where the function stops calling itself (prevents infinite recursion)
Recursive Case — The part where the function calls itself with a smaller/simpler input

⚠️ Always Have a Base Case!

Without a base case, the function calls itself forever → stack overflow → program crash. Every recursive function MUST have a base case that eventually terminates.

How Recursion Works – Call Stack

Each recursive call is added to the call stack. When the base case is reached, functions return one by one (unwinding the stack).

Concept – Countdown

void countdown(int n) {
    if (n == 0) {                    // Base case
        printf("Blastoff!\n");
        return;
    }
    printf("%d... \n", n);
    countdown(n - 1);               // Recursive call
}
// countdown(3) → countdown(2) → countdown(1) → countdown(0)
// Then returns back: 0 done → 1 done → 2 done → 3 done

3... 2... 1... Blastoff!

Factorial using Recursion

Factorial: 5! = 5 × 4 × 3 × 2 × 1 = 120. Recursively: n! = n × (n-1)!, base: 0! = 1

C Language – Recursive Factorial

#include <stdio.h>

long long factorial(int n) {
    if (n <= 1) return 1;          // Base case: 0! = 1! = 1
    return n * factorial(n - 1);   // Recursive case
}

int main() {
    int n;
    printf("Enter n: ");
    scanf("%d", &n);
    printf("%d! = %lld\n", n, factorial(n));
    return 0;
}

Enter n: 6 6! = 720

How it works for factorial(4):

Trace

factorial(4)
  → 4 * factorial(3)
      → 3 * factorial(2)
          → 2 * factorial(1)
              → returns 1  (base case!)
          → returns 2 * 1 = 2
      → returns 3 * 2 = 6
  → returns 4 * 6 = 24

Fibonacci Series using Recursion

Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21... Each term = sum of previous two. F(n) = F(n-1) + F(n-2). Base: F(0) = 0, F(1) = 1

C Language – Recursive Fibonacci

#include <stdio.h>

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
}

int main() {
    int n;
    printf("How many terms? ");
    scanf("%d", &n);
    printf("Fibonacci: ");
    for (int i = 0; i < n; i++)
        printf("%d ", fibonacci(i));
    printf("\n");
    return 0;
}

How many terms? 8 Fibonacci: 0 1 1 2 3 5 8 13

Sum of Digits using Recursion

C Language

#include <stdio.h>

int sumDigits(int n) {
    if (n == 0) return 0;          // Base case
    return (n % 10) + sumDigits(n / 10); // Recursive
}

int main() {
    int num;
    printf("Enter number: ");
    scanf("%d", &num);
    printf("Sum of digits: %d\n", sumDigits(num));
    return 0;
}

Enter number: 12345 Sum of digits: 15

Power Function using Recursion

C Language – power(base, exp)

#include <stdio.h>

long long power(int base, int exp) {
    if (exp == 0) return 1;          // Base case: x^0 = 1
    return base * power(base, exp - 1); // x^n = x * x^(n-1)
}

int main() {
    printf("2^10 = %lld\n", power(2, 10));
    printf("3^5  = %lld\n", power(3, 5));
    return 0;
}

2^10 = 1024 3^5 = 243

Recursion vs Iteration

Feature	Recursion	Iteration (Loop)
Code length	Usually shorter	Can be longer
Readability	Better for tree/graph problems	Better for simple loops
Memory	More (call stack)	Less
Speed	Slower (function call overhead)	Faster
Risk	Stack overflow if no base case	Infinite loop if bad condition
Best for	Trees, graphs, divide & conquer	Simple counting, arrays

Summary

Recursion = a function calling itself
Every recursive function needs: Base Case + Recursive Case
Without a base case → infinite recursion → stack overflow
Each call is added to the call stack; base case unwinds it
Common recursive problems: factorial, Fibonacci, sum of digits, power, GCD
Use iteration when performance matters; use recursion when clarity matters

🏋️ Practice

Write recursive functions: (1) GCD of two numbers (2) Reverse a string (3) Check if string is palindrome (4) Binary search (5) Print all permutations of a string

Frequently Asked Questions

What is recursion in C?

Recursion is when a function calls itself to solve a problem by breaking it into smaller versions of the same problem. Each call works on a simpler input until it reaches a base case that stops the recursion.

What is a base case in recursion?

The base case is the condition that stops a recursive function from calling itself further, giving a direct answer for the simplest input. Without a correct base case, the function would call itself endlessly and eventually crash.

What is the difference between recursion and iteration?

Recursion solves a problem by repeated function calls, while iteration uses loops. Recursion can be more elegant for naturally recursive problems like tree traversal, but it uses extra memory for each call; iteration is usually more memory-efficient.

What causes stack overflow in recursion?

A stack overflow happens when recursion goes too deep — often because the base case is missing or never reached — so each call keeps adding to the call stack until it runs out of space and the program crashes.

What are common examples of recursion in C?

Classic recursive examples include factorial, Fibonacci numbers, the greatest common divisor, the Tower of Hanoi, and traversing data structures like trees and linked lists. These problems have a natural "solve a smaller version" structure that suits recursion.

← Back to C Tutorial

💻 Live Code Editor

This page's programs are ready here — run them, edit them, and learn. No installation needed.

Powered by OneCompiler. The code loads into the editor automatically — press Run to see the output. If the editor does not open, open it in a new tab.