Recursion and tracing recursive algorithms

How recursion works

A recursive subroutine is one that calls itself. Every recursive subroutine needs:

• a base case: a condition where it returns a result without calling itself, which stops the recursion;
• a recursive case: where it calls itself with an argument that moves towards the base case.

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

The call stack

Each call pushes a stack frame holding its parameter, local variables and return address. Calls go down until the base case; then each call returns its value to the one that called it, popping frames in reverse order.

factorial(5) calls factorial(4), which calls factorial(3), factorial(2), factorial(1). factorial(1) returns 1; then 2 x 1 = 2, 3 x 2 = 6, 4 x 6 = 24, 5 x 24 = 120.

If there is no base case, or it is never reached, frames keep being pushed until memory runs out: a stack overflow.

Benefits and drawbacks

Benefits: elegant, short code for problems that are naturally self-similar, such as tree traversal, binary search, divide-and-conquer sorting and fractals.

Drawbacks: each call uses memory for a stack frame and time to set up, so recursion is often slower and more memory-hungry than a loop (iteration); deep recursion can overflow the stack; it can be harder to trace and debug.

Worked example

Trace power(2, 4) where power(b, e) returns 1 if e == 0, otherwise b * power(b, e - 1).

1. power(2, 4) = 2 * power(2, 3)
2. power(2, 3) = 2 * power(2, 2)
3. power(2, 2) = 2 * power(2, 1)
4. power(2, 1) = 2 * power(2, 0)
5. power(2, 0) = 1 (base case)
6. Unwinding: 2, 4, 8, 16

Answer: 16

Check yourself

1. Using factorial(n) = 1 if n <= 1, else n * factorial(n - 1), what does factorial(6) return?
   Show answer

   720. 6 x 5 x 4 x 3 x 2 x 1 = 720.

2. How many calls to factorial are made in total when factorial(5) is called (including the first call)?
   Show answer

   5. factorial(5), (4), (3), (2), (1): 5 calls.

3. ```python def s(n): if n < 10: return n return n % 10 + s(n // 10) ``` What does s(4729) return?
   Show answer

   22. 9 + s(472) = 9 + 2 + s(47) = 9 + 2 + 7 + 4 = 22.

4. ```python def m(n): if n == 0: return 0 return n % 2 + m(n // 2) ``` What does m(13) return?
   Show answer

   3. 13 is 1101 in binary; the function counts the 1 bits: 3.

5. Using power(b, e) = 1 if e == 0, else b * power(b, e - 1), what does power(3, 4) return?
   Show answer

   81. 3 x 3 x 3 x 3 = 81.

6. What is the purpose of the base case in a recursive function?
   • To make the function call itself twice
   • To stop the recursion by returning a value without another call
   • To store the return address
   • To speed up the loop
   Show answer

   To stop the recursion by returning a value without another call. Without it the calls never end.

7. A recursive function has no base case. What will happen when it is called?
   • It returns 0
   • It runs exactly once
   • It becomes an iterative loop automatically
   • It keeps calling itself until the call stack runs out of memory (stack overflow)
   Show answer

   It keeps calling itself until the call stack runs out of memory (stack overflow). Each call adds a frame; memory is finite.

8. Which is a drawback of recursion compared with iteration?
   • It cannot solve problems involving trees
   • It cannot return a value
   • Each call needs a new stack frame, using more memory
   • It never terminates
   Show answer

   Each call needs a new stack frame, using more memory. Stack frames cost memory and time.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary/Advanced Level in Computer Science specification (2026)
• Pearson Edexcel IAL Computer Science IAS sample assessment materials (Unit 1, WCP01)

Last updated 8 November 2026. Spotted a mistake? Tell us.