Skip to content
StudyFame

Recursion in C

Stand between two mirrors and you see a reflection inside a reflection inside a reflection. Recursion is like that: a function that calls itself to solve a smaller copy of the same problem.

Recursion confuses many students. In this lesson you will understand it in three ideas: the base case, the recursive case, and the call stack, traced step by step.

What You Will Learn

  • What recursion is.
  • The base case and the recursive case.
  • How the call stack stores each call.
  • A countdown and a power (xⁿ) program.
  • What causes a stack overflow.

Recursion in C Explained

Exam definition: Recursion is a process in which a function calls itself directly or indirectly. A recursive function must have a base case (a condition where it stops calling itself) and a recursive case (where it calls itself with a smaller problem).

The two parts of every recursive function

PartJobIn sum(n) = 1 + 2 + ... + n
Base caseThe smallest problem, answered directly. Stops the recursion.if (n == 0) return 0;
Recursive caseSolves the problem using a smaller version of itself.return n + sum(n - 1);

Memory trick: Recursion is like Russian dolls: open a doll, find a smaller doll inside, keep opening (recursive case) until you reach the tiniest doll that doesn't open (base case). Then you put them back together one by one (the returns).

Syntax of a Recursive Function

return_type func(parameters)
{
    if (base_condition)
        return base_value;                 /* base case: stop */
    return ... func(smaller_problem) ...;  /* recursive case */
}

Example 1: Countdown and Sum Using Recursion

#include <stdio.h>

void countdown(int n)
{
    if (n == 0)                 /* base case */
    {
        printf("Go!\n");
        return;
    }
    printf("%d ", n);
    countdown(n - 1);           /* recursive case */
}

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

int main(void)
{
    countdown(3);
    printf("sum(3) = %d\n", sum(3));
    return 0;
}

Output

3 2 1 Go!
sum(3) = 6

How the Call Stack Works (Tracing sum(3))

Every function call gets a stack frame: a box on the call stack that holds its own n. New calls go on top; when a call returns, its box is removed.

StepCallWhat it doesStack (top first)
1sum(3)needs 3 + sum(2), waitssum(3)
2sum(2)needs 2 + sum(1), waitssum(2), sum(3)
3sum(1)needs 1 + sum(0), waitssum(1), sum(2), sum(3)
4sum(0)base case: returns 0sum(0), sum(1), sum(2), sum(3)
5back in sum(1)returns 1 + 0 = 1sum(1), sum(2), sum(3)
6back in sum(2)returns 2 + 1 = 3sum(2), sum(3)
7back in sum(3)returns 3 + 3 = 6sum(3) → empty

Going down, each call waits for a smaller one. At the base case, the answers come back up, one by one. This is called winding and unwinding.

Code Explanation

  1. countdown(3) prints 3, then calls countdown(2), which prints 2, and so on.
  2. countdown(0) hits the base case, prints "Go!" and returns. Nothing more is printed on the way back.
  3. sum(3) keeps calling sum with a smaller n until n is 0, then adds the results while returning: 0 → 1 → 3 → 6.

Example 2: Power of a Number (xⁿ) Using Recursion

#include <stdio.h>

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

int main(void)
{
    int x, n;

    printf("Enter base and exponent: ");
    scanf("%d %d", &x, &n);

    printf("%d^%d = %lld\n", x, n, power(x, n));
    return 0;
}

Output

Enter base and exponent: 2 10
2^10 = 1024

The rule xn = x × xn−1 turns a big problem into a smaller one until n reaches 0. The two most famous recursion programs are factorial using recursion in C and the Fibonacci series using recursion.

Important Points to Remember

  • Recursion = a function calling itself.
  • Every recursive function needs a base case to stop.
  • The recursive case must move towards the base case (n − 1, n / 10...).
  • Each call gets its own stack frame with its own variables.
  • No base case → infinite recursion → stack overflow (crash).

Common Mistakes Beginners Make

MistakeWhat happensFix
No base caseInfinite recursion → stack overflow / segmentation faultAlways write the base case first
Recursive call doesn't get smaller (sum(n) instead of sum(n - 1))Never reaches the base caseMove towards the base case
Forgetting return before the recursive callThe result is lost; garbage valuereturn n + sum(n - 1);
Using recursion for huge inputs (like sum(1000000))Stack overflowUse a loop for very deep problems

Recursion in C Practice Questions

  1. What is recursion? What are its two essential parts?
  2. What is a base case? What happens without it?
  3. What is the call stack?
  4. Trace power(3, 3) step by step.
  5. What is the output of countdown(2) from Example 1?
Show answers
  1. A function calling itself. Parts: base case and recursive case.
  2. The condition where the function stops calling itself and returns directly. Without it, recursion never ends and causes a stack overflow.
  3. The memory area where each function call's local variables are stored as frames; new calls are pushed on top and removed when they return.
  4. power(3,3) = 3 × power(3,2) = 3 × 3 × power(3,1) = 3 × 3 × 3 × power(3,0) = 27 × 1 = 27.
  5. 2 1 Go!

Coding Exercise

Write a recursive function int count_digits(int n) that returns the number of digits in n. (Hint: base case when n is less than 10.) Test with 70345.

Show solution
#include <stdio.h>

int count_digits(int n)
{
    if (n < 10)
        return 1;
    return 1 + count_digits(n / 10);
}

int main(void)
{
    printf("Digits in 70345 = %d\n", count_digits(70345));
    return 0;
}
Digits in 70345 = 5

Quick Quiz: Recursion in C (MCQ)

  1. A recursive function is a function that:

    A) Calls main()   B) Calls itself   C) Has a loop   D) Returns void

  2. Which part stops the recursion?

    A) Recursive case   B) Base case   C) printf   D) main

  3. Recursion without a base case causes:

    A) Compile error   B) Stack overflow   C) Correct output   D) Faster code

  4. Value of sum(4) from Example 1:

    A) 4   B) 6   C) 10   D) 24

  5. Function calls are stored in the:

    A) Heap   B) Call stack   C) Hard disk   D) Register only

Show answers
  1. B: calls itself.
  2. B: the base case.
  3. B: stack overflow.
  4. C: 10 (4 + 3 + 2 + 1 + 0).
  5. B: the call stack.

Quick Revision for Exams and Interviews

Read this before your exam. The highlighted words are the answer.

Must-remember facts

RecursionFunction calling itself
Base caseStops the recursion
Recursive caseCalls itself with a smaller problem
Stored inCall stack (one frame per call)
No base caseStack overflow
sum(n)n == 0 ? 0 : n + sum(n - 1)
power(x, n)n == 0 ? 1 : x * power(x, n - 1)

Frequently asked questions

What is a base case in recursion?
The condition where the function stops calling itself and returns a direct answer.
What is stack overflow?
When too many calls fill the call stack, usually because the base case is missing or never reached.
What are direct and indirect recursion?
Direct: f calls f. Indirect: f calls g and g calls f.
Where is recursion useful?
Problems that split into smaller copies: factorial, Fibonacci, trees, Tower of Hanoi, merge sort.

Remember

  • Recursion = Russian dolls: open until the tiniest (base case), then close back.
  • Base case first, then the smaller call.

Next Topic

Next lesson: Recursion vs Iteration in C. You will compare recursion with loops and learn when to use which.