A-level Computer Science revision · Programming

Recursion

The idea

A recursive subroutine calls itself. It must have a base case that stops the recursion, and each call must move towards it. Each call adds a frame to the call stack, so deep recursion can cause a stack overflow. Recursion can be elegant for problems like tree traversal, but iteration often uses less memory.

  1. Identify the base case.
  2. Identify the recursive call and how it shrinks the problem.
  3. Trace using the call stack.

Watch out Without a base case, recursion never stops and causes a stack overflow.

See it worked

Worked example

What does fact(4) return if fact(n) = 1 when n = 0, else n * fact(n − 1)?

  1. fact(4) = 4 × fact(3) = 4 × 3 × fact(2).
  2. = 4 × 3 × 2 × 1 × fact(0).
  3. = 24.

Answer 24

Your turn

Question 12 marks

f(n) returns 0 if n = 0, else n + f(n − 1). What does f(5) return?

Question 21 mark

What causes a stack overflow in a recursive program?

Choose one
Question 32 marks

Give one advantage of recursion over iteration.

Write your answer, then see a model answer
  1. Name the advantage.
  2. Give an example.

Answer Recursive code can be shorter and closer to the problem's natural definition, such as traversing a tree.

A-level Computer Science Pro, OCR H446

A-level Computer Science Pro

£119 once

Price rises to £199 on 1 January. Save £80 by joining before then.

At least 12 months of access

By paying you agree to our Terms and get access straight away, which ends your 14-day cancellation right.

No VAT is charged.

Independent practice for OCR A-level Computer Science (H446), not endorsed by OCR.

Privacy · Terms