AeroLab Reading room

CS / A2 level

Recursion, complexity and computational thinking

Recursion solves a problem through smaller instances, requiring base cases and progress toward them. A call stack records suspended work, so elegant recursive code may use substantial memory.

Learning objectives

The big idea

Recursion solves a problem through smaller instances, requiring base cases and progress toward them. A call stack records suspended work, so elegant recursive code may use substantial memory.

Complexity compares how resource use grows with input size. Big-O describes a bound, not an exact runtime; linear, logarithmic and quadratic growth matter more as inputs become large.

Equations and relationships

1+2+⋯+n=n(n+1)21+2+\cdots+n=\frac{n(n+1)}2

A closed-form alternative to a linear summation loop.

Worked example

A loop compares every pair in an n×n grid. How many comparisons for n=10?

Follow the solution

There are 10 choices in each dimension, giving 10×10=100 comparisons.

Investigate and explain

Predict the worked result before calculating. Change one input, record the new result, and explain which assumptions still hold.

Use the prediction activity below; a local model appears only where it supports this topic.

Open the interactive investigation

Check your understanding

1. What must a terminating recursive method include?

  1. A reachable base case
  2. A global variable always
  3. A network connection
Check the answer and reasoning

A reachable base case

Recursive calls must reduce the problem until a non-recursive return is reached.

2. A loop compares every pair in an n×n grid. How many comparisons for n=10?

  1. 10
  2. 100
  3. 20
Check the answer and reasoning

100

There are 10 choices in each dimension, giving 10×10=100 comparisons.

3. Does O(n²) specify exactly n² machine instructions?

  1. Yes
  2. Only for sorting
  3. No
Check the answer and reasoning

No

Asymptotic bounds ignore fixed factors and lower-order terms; they describe growth rather than an exact count.