Programming Techniques and Computational Methods

1 Explain what is meant by recursion and state what every recursive subroutine must include. 3

One mark for each of the following, to a maximum of 3.

• A subroutine that calls itself
• It must include a base case that returns without recursing
• And a general case moving towards the base case

Model answer. Recursion is a technique in which a subroutine calls itself in order to solve a smaller instance of the same problem. Every recursive subroutine must contain a base case, which is a condition under which it returns a value directly without calling itself again, since this is what stops the process. It must also contain a general case in which it calls itself with an argument that has moved closer to the base case, guaranteeing that the base case is eventually reached. Without a correct base case, or with a general case that never approaches it, the recursion continues indefinitely until the available stack space is exhausted and a stack overflow occurs.

2 Compare recursion and iteration as ways of solving a repeated problem. 5

One mark for each of the following, to a maximum of 5.

• Recursion is a subroutine calling itself, iteration uses a loop
• Recursion often expresses tree and divide and conquer problems more naturally
• Each recursive call creates a stack frame, so memory use grows with depth
• Iteration uses constant memory and is generally faster
• Recursion risks stack overflow where iteration risks an infinite loop

Model answer. Recursion solves a problem by having a subroutine call itself with a smaller version of the same problem, while iteration solves it by repeating a block of code within a loop. The main advantage of recursion is expressiveness: problems that are themselves recursive in structure, such as traversing a binary tree, sorting by divide and conquer or exploring a graph depth first, translate into remarkably short and clear recursive code, whereas the iterative equivalents require an explicit stack and are considerably harder to follow. The cost is memory and speed. Every recursive call creates a new stack frame holding its parameters, local variables and return address, so memory consumption grows in proportion to the depth of recursion, and if that depth is large the stack is exhausted and the program crashes with a stack overflow. Iteration uses a constant amount of memory regardless of how many times it repeats and avoids the overhead of function calls, so it is generally faster. The failure modes differ correspondingly: badly written recursion overflows the stack, while a badly written loop runs forever. In practice recursion is chosen when it makes the solution genuinely clearer and the depth is bounded, and iteration when performance or memory matters or the depth could be large.

3 Explain the difference between passing a parameter by value and passing it by reference. 4

One mark for each of the following, to a maximum of 4.

• By value a copy of the data is passed to the subroutine
• Changes made inside the subroutine do not affect the original
• By reference the memory address of the data is passed
• Changes made inside the subroutine do affect the original, and no copy is made so it is efficient for large data

Model answer. When a parameter is passed by value, a copy of the data is created and given to the subroutine, so the subroutine works on that copy and any changes it makes are discarded when it returns, leaving the caller's variable untouched. This is safer, because the subroutine cannot produce unexpected side effects, but copying a large data structure such as an array of a million elements costs both time and memory. When a parameter is passed by reference, the memory address of the original data is passed instead, so the subroutine operates directly on the caller's variable and any modification it makes persists after the subroutine returns. This is efficient for large structures, since nothing is copied, and it allows a subroutine to return several results by modifying the variables it was given. The corresponding risk is that changes propagate outwards, so a subroutine can alter data the caller did not expect it to touch, which makes reasoning about the program harder.

4 Explain what a heuristic is and give an example of a situation where one would be used. 4

One mark for each of the following, to a maximum of 4.

• A rule of thumb that produces an acceptable solution quickly
• It does not guarantee the optimal solution
• It is used where finding the optimal solution would take unacceptably long
• Gives a valid example such as route finding or the travelling salesman problem

Model answer. A heuristic is a rule of thumb that guides a search towards a good solution quickly, without guaranteeing that the solution found is the best one available. It is used where finding the genuinely optimal answer would require exploring so many possibilities that the computation would take an unacceptable amount of time, or would be entirely infeasible. Route finding is a clear example. A satnav could in principle evaluate every possible sequence of roads between two points and pick the shortest, but the number of possibilities in a real road network is astronomically large. Instead the A star algorithm uses a heuristic, typically the straight line distance from a node to the destination, to decide which routes look most promising and explore those first, discarding directions that lead away from the target. The result is found in a fraction of a second and is almost always optimal or very close to it, and a driver waiting at a junction is far better served by a good answer immediately than a perfect one in an hour.

5 A student writes a recursive function that calculates the sum of the numbers from 1 to n, but it causes a stack overflow when n is 100000. Explain why and suggest a solution. 4

One mark for each of the following, to a maximum of 4.

• Each recursive call adds a stack frame to the call stack
• With 100000 calls the stack space available is exhausted
• Suggests rewriting the function iteratively using a loop
• An iterative version uses constant memory regardless of n

Model answer. Every time the function calls itself, a new stack frame is pushed onto the call stack containing that call's parameters, its local variables and the address to return to when it finishes. None of these frames can be removed until the recursion reaches its base case and the calls begin returning, so at the deepest point there are one hundred thousand frames on the stack simultaneously. The stack is allocated a fixed and comparatively modest amount of memory, typically a few megabytes, so it is exhausted long before that depth is reached and the program crashes with a stack overflow. The solution is to rewrite the function iteratively, using a loop that maintains a running total from 1 to n. This uses a constant amount of memory no matter how large n becomes, because there is only ever one stack frame, and it is also faster because it avoids the overhead of a hundred thousand function calls. For this particular problem there is an even better answer, since the sum of the first n integers is given directly by the formula n multiplied by n plus one, divided by two, which computes the result in a single operation.