Recursion

Some problems are easiest to solve by solving a smaller copy of themselves — a function that calls itself. That's recursion, and once it clicks it becomes one of the most elegant tools in programming. By the end of this lesson you'll write recursive functions with a proper base case, trace how the call stack unwinds, and recognize when recursion beats a loop (and when it doesn't).

Learn Recursion in our free C++ course — a beginner-friendly interactive lesson with worked examples, a practice exercise and a quick recall.

Part of the free C++ course at LearnCodingFast — hands-on lessons with examples you run in your browser, plus practice exercises and a quick quiz.

Imagine standing in a long queue and wanting to know your position. You can't see the front, so you ask the person in front of you "what's your number?" — they don't know either, so they ask the person ahead of them , and so on. Eventually the question reaches the very first person (the base case ), who says "I'm number 1". That answer travels back down the line, each person adding one, until it reaches you. That's recursion: each step delegates a smaller version of the question, and the answers flow back once the base case is hit.

Every recursive function needs both . Miss the base case and you get infinite recursion → stack overflow.

1. The Classic: Factorial

Factorial is the "hello world" of recursion. n! equals n times (n-1)! , and the chain stops at 1! = 1 . Notice the two pieces: the base case ( if (n <= 1) return 1; ) that ends the recursion, and the recursive case that calls factorial with a smaller argument. Read the comment that traces how factorial(5) unfolds.

2. Recursion That Returns Nothing

Recursion isn't only for computing values — a void function can recurse to repeat an action. This countdown prints a number, then calls itself with n - 1 until it reaches the base case at 0 . The key, as always: each call must move closer to the base case, or it never stops.

Your turn. Complete the recursive case so sumTo(n) adds 1 + 2 + ... + n :

These lines form a complete recursive factorial function. Put them in the correct order:

Open the function (B), check the base case first so recursion can terminate (C), then the recursive case multiplies by the smaller call (A), and close the brace (D). The base case must come before the recursive call.

3. Multiple Recursive Calls: Fibonacci

A recursive function can call itself more than once . The Fibonacci sequence — where each number is the sum of the previous two — needs two base cases ( fib(0)=0 , fib(1)=1 ) and two recursive calls. It's beautifully concise, but watch out: this naive version recomputes the same values over and over, so it becomes very slow for large n . That's a real lesson about recursion's cost.

4. Divide and Conquer: Fast Power

Recursion shines in divide-and-conquer , where each call shrinks the problem by half rather than by one. Fast exponentiation computes base^exp in O(log n) by squaring the result of power(base, exp/2) . Halving the exponent each step means even 2^1000 takes only about ten calls — a huge improvement over multiplying one at a time.

Each function call pushes a stack frame holding its parameters and local variables. A recursive call pushes another frame before the current one finishes, so the frames pile up until the base case is reached — then they unwind, each returning its result to the caller below it:

Because the stack is finite, very deep recursion causes a stack overflow . Any recursion can be rewritten as a loop (sometimes with your own explicit stack). Choose recursion when it expresses the structure of the problem clearly — trees, graphs, divide-and-conquer — and a loop when the task is simple, deep, or performance-critical.

Predict the output before revealing the answer.

No base case — it recurses forever (n keeps shrinking past 0), exhausting the stack and crashing with a stack overflow.

5 — the sequence is 0,1,1,2,3,5,... and fib(5) is the index-5 value, 5.

Check a word from both ends inward — a perfect fit for recursion. The outline gives you the base case and the recursive step.

Practice quiz

What is recursion?

A loop that runs forever
Two functions that call each other once
A function that calls itself to solve a smaller version of the same problem
A function with no return value

Answer: A function that calls itself to solve a smaller version of the same problem. Recursion is a function calling itself on a smaller subproblem until it reaches a base case.

What two parts does every recursive function need?

A base case and a recursive case
A loop and a counter
A constructor and a destructor
Two return statements

Answer: A base case and a recursive case. Every recursion needs a base case that stops it and a recursive case that moves toward the base case.

What does factorial(5) return for long long factorial(int n){ if(n<=1) return 1; return n*factorial(n-1); }?

Answer: 120. 5! = 5*4*3*2*1 = 120.

What happens if a recursive function has no base case?

It returns 0
It recurses forever and overflows the call stack (stack overflow)
The compiler refuses to build it
It runs exactly once

Answer: It recurses forever and overflows the call stack (stack overflow). Without a base case the function never stops calling itself, exhausting the finite call stack and crashing.

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

Answer: 10. It sums 4 + 3 + 2 + 1 + 0 = 10.

How many recursive calls does the Fibonacci function fib(n) = fib(n-1) + fib(n-2) make per non-base call, and how many base cases does it need?

One call, one base case
Three calls, one base case
Two calls, two base cases (fib(0)=0 and fib(1)=1)
Two calls, no base case

Answer: Two calls, two base cases (fib(0)=0 and fib(1)=1). Fibonacci calls itself twice and needs two base cases: fib(0)=0 and fib(1)=1.

What does fib(5) return for int fib(int n){ if(n<2) return n; return fib(n-1)+fib(n-2); }?

Answer: 5. The sequence is 0,1,1,2,3,5,... and the index-5 value is 5.

Why is the naive recursive Fibonacci slow for large n?

It uses too much memory for the result
It cannot use the base case
Recursion is always O(n^2)
It recomputes the same subproblems many times (exponential blowup)

Answer: It recomputes the same subproblems many times (exponential blowup). The naive version recomputes overlapping subproblems repeatedly; memoization or iteration fixes it.

Fast exponentiation power(base, exp) halves the exponent each call. What is its time complexity?

O(n)
O(log n)
O(n^2)
O(1)

Answer: O(log n). Halving the exponent each step (divide and conquer) gives O(log n) calls.

What is wrong with int bad(int n){ return n * bad(n - 1); }?

It multiplies in the wrong order
It should use += instead of *
It has no base case, so it recurses forever and overflows the stack
n must be a long long

Answer: It has no base case, so it recurses forever and overflows the stack. There is no base case to stop the recursion, so n keeps shrinking past 0 and the stack overflows.