Recursion: factorial, Fibonacci and Euclid's GCD

Early October 2026: in Year 3 computer science classes at the Italian technical institutes (and in Year 3 of the applied-sciences liceo scientifico), after loops, arrays and functions comes recursion: a function that calls itself. It is usually covered between October and November, and the practical test in the lab falls five to nine weeks from now. The topic is scary because the code is only a few lines long and it looks like magic. It isn’t: all you need is one rule and a method for tracing by hand.

What recursion is

A function is recursive if, to solve a problem of size $n$, it solves the same problem on a smaller size and then combines the result. Every recursive function has two compulsory parts.

• Base case: the situation so small that the answer is already known, with no further calls (for the factorial: $0!=1$).
• Recursive step: it reduces the problem and calls the function again on a value closer to the base case (for the factorial: $n!=n\cdot (n-1)!$).

If either is missing, the program does not work. Before writing code, write these two lines in plain words.

The call stack

When a function calls another, the first one waits: the computer puts it on a stack and comes back to it when the second has finished. With recursion the stack grows at every call and empties when you reach the base case and the values come back. Tracing this stack by hand is the skill that every test checks.

Trace of factorial(4)

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

Result: $4!=24$. Note that the products are computed on the way back, from the bottom up: until you reach factorial(0), no multiplication has been done.

The same function in Python:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(4))   # 24

Fibonacci: why the naive version is slow

The sequence: $F_0=0$, $F_1=1$, and every term is the sum of the two before it. Here there are two base cases.

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

print(fib(5))   # 5

The recursive step calls itself twice: each call generates two more, and many are repeated. Let’s count them for fib(5). If $C(n)$ is the total number of calls made by fib(n), then $C(0)=C(1)=1$ and $C(n)=1+C(n-1)+C(n-2)$:

So fib(5) makes 15 calls to return 5. Inside, fib(3) is computed twice and fib(2) three times. With $n=40$ the calls number in the hundreds of millions: that is why the program “freezes”. The cost grows exponentially (if you have already seen Big-O notation, this is the difference between $O(n)$ and an exponential cost). The iterative version, which keeps only the last two values, takes $n$ steps:

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_iter(5))   # 5

In C++ you can check the count with a global counter:

#include <iostream>
using namespace std;

int calls = 0;

int fib(int n) {
    calls++;
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    cout << fib(5) << endl;        // 5
    cout << calls << endl;         // 15
    return 0;
}

Euclid’s GCD

Euclid’s algorithm rests on a property: $\text{gcd}(a,b)=\text{gcd}(b,a\mathrm{mod}b)$, and $\text{gcd}(a,0)=a$. The base case is $b=0$, and the recursive step replaces the pair with a pair in which the second number is smaller: it always gets closer to 0.

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

Let’s redo gcd(48, 18) step by step.

The result comes back up unchanged: $\text{gcd}(48,18)=6$. In this case the recursion is “tail recursion”: nothing is left to do on the way back, and the version with a while loop is equivalent.

Recursion or iteration?

Every recursive function can be written with a loop, and vice versa. Recursion is more natural when the problem has a structure that repeats on itself (trees, halving, factorial, Euclid); iteration is cheaper in memory, because it does not fill the stack. A practical rule for the test: if the question says “recursive”, write it recursively; if it doesn’t say and you are unsure, a loop is almost always safer. But you need to be able to do both.

The mistakes that cost marks

1. Missing base case. The function calls itself forever, the stack fills up and the program stops with a stack overflow error (in Python, RecursionError: the default limit is about a thousand calls).

2. Wrong base case. This is the most insidious one. If you write if (n == 1) return 1; and call factorial(0), the sequence is 0, -1, -2, … and n == 1 is never triggered.

3. Not getting closer to the base case. If in the recursive step you write factorial(n) instead of factorial(n - 1), the call is identical to itself. Or you get the sign wrong and go in the opposite direction.

4. Forgetting the return in front of the call. factorial(n - 1) on its own calculates the value and throws it away.

5. Number overflow. With a 32-bit int, $12!=479001600$ fits, $13!=6227020800$ does not: the result is wrong with no error message. It is not a recursion mistake, but it shows up when you try large values.

Three worked exercises

Exercise 1: recursive power

Write power(b, e) that calculates $b^e$ for $e\ge 0$ without using pow.

Reasoning: $b^0=1$ (base case), $b^e=b\cdot b^{e-1}$ (recursive step; $e$ decreases by 1 and reaches 0).

def power(b, e):
    if e == 0:
        return 1
    return b * power(b, e - 1)

print(power(2, 5))   # 32

Trace of power(2, 5): it goes down to power(2, 0) = 1, then comes back up: $2\cdot 1=2$, $2\cdot 2=4$, $2\cdot 4=8$, $2\cdot 8=16$, $2\cdot 16=32$. Five multiplications, result 32.

Exercise 2: sum of digits

Write a function that, given a positive integer, returns the sum of its digits.

Idea: the last digit is n % 10, the rest of the number is n / 10 (integer division). Base case: if n < 10 the sum is n itself.

#include <iostream>
using namespace std;

int digitSum(int n) {
    if (n < 10) return n;
    return n % 10 + digitSum(n / 10);
}

int main() {
    cout << digitSum(472) << endl;   // 13
    return 0;
}

Trace: digitSum(472) = $2+$ digitSum(47); digitSum(47) = $7+$ digitSum(4); digitSum(4) = 4 (base case). Coming back up: $7+4=11$, then $2+11=13$. Output: 13.

Exercise 3: find the mistake

This code is supposed to calculate the factorial:

int factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n - 1);
}

What happens with factorial(3)? And with factorial(0)?

• factorial(3): 3 → 2 → 1, and n == 1 stops the descent. It comes back up: $2\cdot 1=2$, $3\cdot 2=6$. It works.
• factorial(0): the sequence is 0, -1, -2, -3, … never touching 1. There is no stopping point, and after a few thousand calls the program ends with a stack overflow.

Fix: base case if (n <= 1) return 1;, which covers both 0 and 1 (and, to be safe, negatives, even though in theory the factorial is not defined for them).

Practising: what is on the site

There is not yet a dedicated computer science practice test, and I won’t promise that one is coming. On the site you will find the practice tests page with what exists today, but for recursion the useful practice is something else: take the three exercises above, rewrite them without looking, then trace the stack by hand with pen and paper. If the computer proves you right, you have understood.

Where it connects

Recursion uses everything you have just studied. If loops and arrays still feel slippery, start from nested loops and arrays in Year 3. Tracing the stack only makes sense if you are clear on how a function receives its parameters: you will find that in functions, by value and by reference. And if you want to understand why the naive fib is slow in formal terms, there is complexity and Big-O, written for university but with the same ideas. The general page is computer science.

How we work in lessons

With recursion I always do the same thing: first you write the base case and the step in plain words, then the code, then the hand trace of the stack on a small value, and only after that do you press “run”. If the program gives a result you did not expect, you go back to the trace and look for the step where your prediction and the program diverge. It is not quick at first, but it is the only way to stop writing recursion “by trial and error”. The code we write is yours, in your own editor, with the exercises from your own book.

If you want to work out where to restart, with no commitment, the free 30-minute introductory call on the contact page is the simplest way. For the arrangements there is the pricing page.