Home›Study Resources›Computer Science›
What is recursion in programming?
Computer Science
A-Level

What is recursion in programming?

Recursion is when a subroutine calls itself to solve a smaller version of the same problem. Every recursive function needs a base case that stops the calls, and a general case that moves towards it. Each call is placed on the call stack, so very deep recursion can cause a stack overflow. Example: factorial(n) returns 1 if n = 1, otherwise n × factorial(n − 1). Find factorial(4). factorial(4) = 4 × factorial(3) = 4 × 3 × factorial(2) = 4 × 3 × 2 × factorial(1) = 4 × 3 × 2 × 1 Answer: 24

Recursion is a programming technique in which a subroutine is defined in terms of itself. At A Level, you need to identify the base case and general case, trace recursive calls, and compare recursion with iteration. Recursive solutions can be elegant but use more memory because each call adds a frame to the stack.

Worked example

Using factorial(n): IF n = 1 THEN RETURN 1 ELSE RETURN n × factorial(n − 1), trace factorial(4).

  1. Call factorial(4): n ≠ 1, so return 4 × factorial(3).
  2. Call factorial(3): return 3 × factorial(2).
  3. Call factorial(2): return 2 × factorial(1).
  4. Call factorial(1): base case, return 1.
  5. Unwind: 2 × 1 = 2, then 3 × 2 = 6, then 4 × 6 = 24.

Answer: factorial(4) = 24

Reviewed by

Want one-to-one support?

One-to-one online tuition can help you build confidence in your subject. Find a tutor who teaches your course.

Find a Tutor

Learn face to face in Glasgow

Prefer in-person lessons? Visit the ExpertTutor Glasgow Southside centre.

See the centre