Subroutines and Recursion

A subroutine is a named, reusable block of code that performs a specific task. Subroutines reduce duplication and make programs easier to read, test, and maintain.

Two types:

Type	Returns a value?	AQA keyword
Procedure	No	PROCEDURE
Function	Yes	FUNCTION / RETURN

PROCEDURE greet(name)
    OUTPUT "Hello, " + name
ENDPROCEDURE

FUNCTION square(n)
    RETURN n * n
ENDFUNCTION

// Calling them:
greet("Alice")          // OUTPUT: Hello, Alice
result ← square(5)     // result = 25

A function must always execute a RETURN statement before it ends. A procedure produces effects (output, modifying data) but returns nothing.

Formal parameters are the names listed in the subroutine definition. Actual parameters (arguments) are the values passed when the subroutine is called.

FUNCTION add(a, b)          // a and b are formal parameters
    RETURN a + b
ENDFUNCTION

result ← add(10, 20)        // 10 and 20 are actual parameters

Pass by value — a copy of the value is passed; changing the parameter inside the subroutine does not affect the original variable.

Pass by reference — the address of the variable is passed; changes inside the subroutine do modify the original.

// Pass by value (default in AQA pseudocode)
PROCEDURE doubleVal(x)
    x ← x * 2    // Only changes local copy
ENDPROCEDURE

// Pass by reference
PROCEDURE doubleRef(BYREF x)
    x ← x * 2    // Changes the original variable
ENDPROCEDURE

Local variables are declared inside a subroutine. They exist only while that subroutine is executing and cannot be accessed from outside it.

Global variables are declared outside all subroutines. They are accessible from anywhere in the program.

globalCount ← 0         // Global variable

PROCEDURE increment()
    localTemp ← 1       // Local variable — only exists here
    globalCount ← globalCount + localTemp
ENDPROCEDURE

increment()
OUTPUT globalCount      // 1
OUTPUT localTemp        // ERROR — localTemp is out of scope

Minimise global variables. They create hidden dependencies between subroutines, making programs harder to debug and test. Prefer passing values as parameters.

When a subroutine is called, the processor creates a stack frame on the call stack. The stack frame stores:

• The return address (where execution resumes after the call)
• The local variables declared inside the subroutine
• The parameter values passed to the subroutine

Call: main() → factorial(3) → factorial(2) → factorial(1)

Call stack (top = most recent):
┌──────────────────────────────┐
│ factorial(1): n=1, ret→f(2)  │ ← top
├──────────────────────────────┤
│ factorial(2): n=2, ret→f(3)  │
├──────────────────────────────┤
│ factorial(3): n=3, ret→main  │
├──────────────────────────────┤
│ main()                        │
└──────────────────────────────┘

As each call returns, its frame is popped off the stack. Deep recursion can exhaust stack space, causing a stack overflow.

A recursive subroutine calls itself. Every recursive definition has two components:

1. Base case — a condition under which the subroutine returns without calling itself
2. Recursive case — the subroutine calls itself with a simpler (smaller) input

Without a base case, recursion never terminates and the call stack overflows.

Worked example — factorial:

$n!=\{\begin{array}{ll}1& \text{if }n=0\\ n\times (n-1)!& \text{if }n>0\end{array}$

FUNCTION factorial(n)
    IF n = 0 THEN
        RETURN 1                    // Base case
    ELSE
        RETURN n * factorial(n - 1) // Recursive case
    ENDIF
ENDFUNCTION

Trace for factorial(4):

factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * (1 * factorial(0))))
= 4 * (3 * (2 * (1 * 1)))
= 4 * (3 * (2 * 1))
= 4 * (3 * 2)
= 4 * 6
= 24

The Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, …

FUNCTION fib(n)
    IF n <= 1 THEN
        RETURN n                        // Base cases: fib(0)=0, fib(1)=1
    ELSE
        RETURN fib(n - 1) + fib(n - 2) // Recursive case
    ENDIF
ENDFUNCTION

Trace for fib(4):

fib(4) = fib(3) + fib(2)
       = (fib(2) + fib(1)) + (fib(1) + fib(0))
       = ((fib(1) + fib(0)) + 1) + (1 + 0)
       = ((1 + 0) + 1) + 1
       = 3

Note that fib(2) is computed twice in this trace — a key inefficiency of naïve recursion. This is the motivation for dynamic programming (extra context — not required by AQA 7517).

Aspect	Recursion	Iteration
Code style	Often more concise for naturally recursive problems	Explicit loop; more lines for recursive problems
Memory use	Each call adds a stack frame; risk of stack overflow	Uses a fixed amount of memory
Performance	Function call overhead; recomputation of sub-problems	Generally faster; no call overhead
Best for	Tree/graph traversal, divide-and-conquer, parsing	Simple counting, list processing

1. Missing the base case

Without a base case the subroutine calls itself indefinitely, causing a stack overflow. Always identify the base case before writing the recursive case.

2. Confusing pass by value and pass by reference

Pass by value: changes to the parameter inside the subroutine do not affect the calling code's variable. Pass by reference: they do. State which mechanism you are using when writing pseudocode answers.

3. Assuming local variables persist between calls

Each call creates a new stack frame with fresh local variables. A local variable set in one call is gone after that call returns.

4. Off-by-one errors in base cases

factorial(0) = 1 (not factorial(1) = 1). Using 1 as the base case causes factorial(0) to recurse into factorial(-1) and beyond.