Skip to content

Beginner · Functions and arrays · topic 13 of 60 · 25 min

Recursion

Explanation

A recursive function calls itself on a smaller version of the problem. It needs a base case that stops the recursion and a recursive case that moves toward it. Each call gets its own stack frame; too many nested calls overflow the stack and crash the program (usually a segmentation fault). Naive recursive Fibonacci is very slow; loops are often better in C.

The idea

Some problems are naturally defined in terms of smaller copies of themselves: n! = n × (n − 1)!, the sum of an array is the first element plus the sum of the rest. A recursive function expresses this directly. It must have a base case that answers the smallest problem without calling itself.

c
unsigned long long factorial(unsigned int n) {
    if (n <= 1) return 1;              /* base case */
    return n * factorial(n - 1);       /* recursive case: a smaller problem */
}
/* factorial(5) = 120; factorial(20) = 2432902008176640000 (the largest that fits in 64 bits) */

The call stack, drawn

output
factorial(3)
│  n = 3 → needs factorial(2)
│  │  n = 2 → needs factorial(1)
│  │  │  n = 1 → base case, returns 1
│  │  returns 2 * 1 = 2
│  returns 3 * 2 = 6
6
Each call has its own n in its own stack frame; they finish in reverse order.

A stack frame is the block of memory for one function call: its parameters, local variables and the return address. Frames are pushed on the call stack when a function is called and popped when it returns.

Power and binary search, recursively

c
double power(double base, int exp) {       /* exp >= 0 */
    if (exp == 0) return 1;
    double half = power(base, exp / 2);    /* halve the problem each time: about log2(exp) calls */
    return (exp % 2 == 0) ? half * half : half * half * base;
}

int bsearch_rec(const int a[], int lo, int hi, int target) {
    if (lo > hi) return -1;                /* base case: empty range */
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == target) return mid;
    return (a[mid] < target) ? bsearch_rec(a, mid + 1, hi, target)
                             : bsearch_rec(a, lo, mid - 1, target);
}

Why naive Fibonacci is slow

c
long long fib(int n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }
/* fib(40) makes over 300 million calls: the same values are recomputed again and again.
   A simple loop computes it in 40 steps. */
Careful: Every recursive call uses stack space (typically 8 MB in total on Linux by default, often 1 MB on Windows). A missing or unreachable base case, or a very deep recursion such as summing a 10-million-element list recursively, overflows the stack and the program crashes, usually with "Segmentation fault". In C, prefer loops for simple linear processing, and use recursion for naturally recursive structures (trees, divide-and-conquer).
Think of it like this: Recursion is like a set of nested tiffin boxes: to reach the innermost box, you open each box in turn (each call), and when you find the innermost one (the base case) you close them again in reverse order, carrying the result back out.
Tip: To write a recursive function, first write the base case, then assume the function already works for smaller inputs and use it ("leap of faith"), and finally check that every call really moves toward the base case.

Need help?

Stuck on a word or an idea? Search this course, or every course, and jump straight to the explanation or a worked question.

Try:

Watch the lesson

Recursion · 1/6

Recursion

In this lesson you will write recursive functions, which call themselves.

Prefer a video by a teacher? Find free videos on “recursion in c factorial fibonacci call stack explained” on YouTube ↗

In real life: Folder sizes on a disk

A disk-usage tool (like du on Linux) computes the size of a folder as the size of its files plus the sizes of its sub-folders, which is naturally recursive. Real tools also limit depth or use an explicit stack to avoid stack overflow on extremely deep trees.

c
long long folder_size(const Folder *f) {
    long long total = 0;
    for (int i = 0; i < f->file_count; i++) total += f->files[i].size;
    for (int i = 0; i < f->sub_count; i++) total += folder_size(&f->subs[i]);   /* recursion */
    return total;
}

Practice (0/3 done)

Task 1 · Question

What does f(4) return? int f(int n) { if (n == 0) return 0; return n + f(n - 1); }

Task 2 · Code · Python

The same recursive algorithm in Python, which runs here: write power(base, exp) for whole exp >= 0 using the halving idea (compute power(base, exp // 2) once and square it), without ** or pow.

Task 3 · Practice

Write recursive C functions: int sum_digits(int n) (n >= 0), int is_palindrome(const char *s, int lo, int hi) that compares the outer characters and recurses inward, and an iterative fib(n) with a loop. Test each with at least three inputs including edge cases (0, an empty or one-letter string).

Quick quiz

Question 1

1.What must every recursive function have?

Question 2

2.What usually happens when recursion goes too deep in C?

Question 3

3.Why is naive recursive Fibonacci slow?

Question 4

4.What is a stack frame?

Read more (free)

Before this, learn

This topic builds on these. If something here feels new, open them first.

Open a question to see the answer and why. The first ones are this topic's own quiz, so try the quiz above before you peek.

What must every recursive function have?

Answer: A base case

Without it, recursion never stops.

What usually happens when recursion goes too deep in C?

Answer: A stack overflow, typically a segmentation fault

The call stack runs out of space.

Why is naive recursive Fibonacci slow?

Answer: It recomputes the same values exponentially many times

fib(n-1) and fib(n-2) overlap heavily.

What is a stack frame?

Answer: The memory for one function call: parameters, locals and return address

Frames are pushed and popped on the call stack.

What happens if a recursive function has no reachable base case?Related

Answer: It keeps calling itself until Python raises RecursionError

Every call adds a frame; with no base case the stack grows until the recursion limit (about 1,000 in Python) is hit.

From Recursion: functions that call themselves

Why is the simple recursive Fibonacci slow for n = 45?Related

Answer: It recomputes the same smaller values a huge number of times

The number of calls grows exponentially. A loop or memoisation computes each value once.

From Overloading, default arguments and recursion

What does every recursive function need to stop?Related

Answer: A base case

The base case answers the smallest input directly without calling itself.

From Higher-order functions and recursion

What happens if a recursive function has no base case?Related

Answer: Python raises RecursionError after about 1000 nested calls

The calls keep stacking up until Python's recursion limit stops them with RecursionError.

From Recursion and sorting algorithms

Pass the quiz (60% or more) or mark this topic as done when you are ready.

Your progress is saved on this device only.

Next: Arrays →

Next steps

  1. 2 more topics in “Functions and arrays” before its exam: Arrays, 2D arrays and classic array algorithms.
  2. Module 3 exam: Functions and arrays · 12 questions · 25 min, without help. 5 topics of this module still to finish first.
  3. Then the next module, Strings in C. 60 topics left in the course before the final exam.

← Previous: Scope and storage classes