Recursion and the Call Stack in C and C++

What is Recursion and the Call Stack?

Every recursive function needs a base case and progress toward it.

Important points

Test empty, single-element, duplicate, and already sorted inputs.
Separate correctness from optimization.
Use the standard library in production unless a custom implementation is justified.

See how it works

Press Step to follow each call. New calls go onto the call stack, and each one returns its value to the call that made it.

C and C++ code examples

C

Run code →

main.c

#include <stdio.h>

unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main(void) {
    printf("%llu\n", factorial(6));
}

Result of running the code

C++

Run code →

main.cpp

#include <iostream>

constexpr unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main() {
    constexpr auto value = factorial(6);
    std::cout << value << '\n';
}

Result of running the code

C and C++ comparison

Each call consumes stack space, so the factorial versions use O(n) time and O(n) call-stack space. Large inputs need validation and often an iterative solution.

C

Loops, pointers, lengths, and temporary buffers are written explicitly.

C++

Iterators and standard algorithms separate operations from container representation.

Practice exercises

Run both versions, then modify them to observe the different language guarantees.

Trace each comparison on paper.
Test duplicates and extreme values.
Benchmark the custom implementation against the standard library.

Practice with a challenge

Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.

All challenges