# Algorithm tracing

> CIE A-Level Computer Science · Unit 9: Algorithm design & problem solving
> Source: https://www.owlsprep.com/study/cie-9618-u9-algorithm-tracing/

Algorithm tracing (or dry-running) is a core CIE 9618 Paper 2 skill where you walk through pseudocode line-by-line to record variable changes and predict final output. This guide covers tracing for iterative, nested and recursive algorithms with exam-specific best practices.

**Prerequisites:** [CIE 9618 Pseudocode notation](https://www.owlsprep.com/study/cie-9618-u9-pseudocode-notation/); [Control structures: loops, conditionals and recursion](https://www.owlsprep.com/study/cie-9618-u9-control-structures/)

## Learning objectives

- Trace execution of iterative, nested and recursive algorithms step-by-step
- Record variable values and output at every execution stage correctly
- Avoid common exam traps and maximize marks for tracing questions

## Tracing Iterative Algorithms

**Algorithm Tracing (Dry Run)** — The process of manually simulating an algorithm's execution step-by-step, recording the value of every variable and any output produced at each stage.

> **tip**
>
> The standard exam-friendly way to organize tracing is a table with one column per variable, and one row per execution step. This keeps your work clear for examiners.

**Worked example:** Trace the pseudocode below that calculates the sum of the first 4 positive even numbers, and find the final output:
```
sum ← 0
FOR count ← 1 TO 4
    number ← 2 × count
    sum ← sum + number
NEXT count
OUTPUT sum
```

1. 1. Before entering the loop, initialize the declared variable:
2. sum = 0, count and number are unassigned
3. 2. First loop iteration: count is set to 1
4. number = $2 \times 1 = 2$, sum = $0 + 2 = 2$
5. 3. Second loop iteration: count increments to 2
6. number = $2 \times 2 = 4$, sum = $2 + 4 = 6$
7. 4. Third loop iteration: count increments to 3
8. number = $2 \times 3 = 6$, sum = $6 + 6 = 12$
9. 5. Fourth loop iteration: count increments to 4
10. number = $2 \times 4 = 8$, sum = $12 + 8 = 20$
11. 6. Loop exits after count increments past 4, final output is:
12. $$20$$

> **Exam tip:** Always start your trace table with initial variable values before any loops or conditional blocks run. One mark is almost always awarded for correct initialization.

## Tracing Nested Control Structures

Nested control structures (if statements inside loops, loops inside loops) require extra care to track which level of execution you are at, and which variables are currently being updated.

**Nested Iteration** — A loop that contains another loop (inner loop) inside its body. Each iteration of the outer loop runs the entire inner loop from start to finish.

**Worked example:** Trace the following nested pseudocode and write all output produced:
```
FOR outer ← 2 TO 2
    OUTPUT "2 x: "
    FOR inner ← 1 TO 3
        product ← outer × inner
        OUTPUT product
    NEXT inner
NEXT outer
```

1. 1. Outer loop starts: outer = 2, output the string `2 x: `
2. 2. First inner loop iteration: inner = 1
3. product = $2 \times 1 = 2$, output `2`
4. 3. Second inner loop iteration: inner = 2
5. product = $2 \times 2 = 4$, output `4`
6. 4. Third inner loop iteration: inner = 3
7. product = $2 \times 3 = 6$, output `6`
8. 5. Inner loop exits, outer loop exits. Full output is:
9. `2 x: 2 4 6`

> **warning**
>
> Don't forget to record all output generated at every step, not just the final output. Many exam questions ask for all output produced, so missing intermediate outputs loses marks.

> **Exam tip:** When tracing nested loops, add separate columns for the outer and inner index values to avoid getting lost between iterations.

## Tracing Recursive Algorithms

Recursive algorithms (functions that call themselves with smaller inputs) require tracing each call stack frame separately, to track return values and correctly identify the base case.

**Call Stack Frame** — A separate entry on the call stack for each active recursive call, storing the input parameters and return address for that call.

**Worked example:** Trace the factorial function $fact(n)$ defined below, for input $n=3$, find the final return value:
```
FUNCTION fact(n)
    IF n == 0 THEN
        RETURN 1
    ELSE
        RETURN n * fact(n - 1)
    ENDIF
ENDFUNCTION
```

1. 1. Initial call: $fact(3)$, $n=3 \neq 0$ so need to compute $3 \times fact(2)$
2. 2. New call: $fact(2)$, $n=2 \neq 0$ so need to compute $2 \times fact(1)$
3. 3. New call: $fact(1)$, $n=1 \neq 0$ so need to compute $1 \times fact(0)$
4. 4. New call: $fact(0)$, hit base case, return 1
5. 5. Unwind stack: $fact(1)$ returns $1 \times 1 = 1$
6. 6. Unwind stack: $fact(2)$ returns $2 \times 1 = 2$
7. 7. Unwind stack: $fact(3)$ returns $3 \times 2 = 6$
8. Final return value is:
9. $$6$$

> **Exam tip:** Always draw the call stack clearly, labeling each call with its input parameter value. Examiners need to see you understand the order of execution and unwinding.

## Common pitfalls

- **Wrong:** Only writing the final value of each variable, not updating after every step
  - Why it fails: Examiners award 70-80% of marks for intermediate steps, so you lose most marks even if the final output is correct
  - Correct: Update every variable in your trace table every time its value changes, no matter how trivial the change seems
- **Wrong:** Off-by-one errors in FOR loops, stopping one iteration too early
  - Why it fails: CIE pseudocode FOR loops are inclusive of both start and end bounds, so you must run when the counter equals the end value
  - Correct: Calculate number of iterations as (end - start + 1) to confirm you have the correct number of steps
- **Wrong:** Forgetting to reset the inner loop counter for each outer loop iteration in nested loops
  - Why it fails: This leads to incorrect inner loop execution and wrong variable values for all subsequent steps
  - Correct: Add separate columns for outer and inner counters, and explicitly reset the inner counter each outer iteration
- **Wrong:** Calculating the final return value before reaching the base case for recursion
  - Why it fails: Recursive calls depend on the return value of deeper calls, so calculating early leads to wrong results
  - Correct: Draw all calls from initial input down to the base case first, then unwind back upwards to calculate return values

## Cheatsheet

| Algorithm Type | Key Action | Exam Mark Tip |
| --- | --- | --- |
| Iterative | Initialize variables first, update every step | 1 mark for correct initialization |
| Nested Loop | Separate columns for outer/inner counters | Iterations = end - start + 1 |
| Recursive | Draw stack down to base case, unwind up | Marks for each correct call frame |
| Any Tracing | Record all output, not just final result | Missing output = lost marks |

## What's next

Algorithm tracing is a foundational skill for all algorithm problems in CIE 9618, from sorting and searching to recursive problem solving. Mastering step-by-step tracing not only helps you correctly answer dedicated tracing questions, but also lets you debug your own pseudocode when writing original algorithms for open-ended problem solving questions, which carry the majority of marks on Paper 2. Consistent tracing practice builds speed and helps you avoid common errors that cost easy marks in the exam.

- [Data types & structures](https://www.owlsprep.com/study/cie-9618-u10-overview/)
- [Primitive Data Types](https://www.owlsprep.com/study/cie-9618-u10-primitive-data-types/)
- [Arrays](https://www.owlsprep.com/study/cie-9618-u10-arrays/)

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/cie-9618-u9-algorithm-tracing/