Programming Techniques and Computational Methods
Recursion, parameter passing, scope, IDE features, and every computational method on the specification with when each applies.
Programming techniques
Recursion
A subroutine that calls itself. Every recursive solution needs:
- A base case that returns without recursing, stopping the process
- A general case that calls itself with input moving towards the base case
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # general caseEach call adds a stack frame holding parameters, local variables and the return address. Too many nested calls exhaust the stack, producing a stack overflow.
| Recursion | Iteration | |
|---|---|---|
| Expressiveness | Very natural for tree and graph problems, and divide and conquer | Natural for repeated sequential work |
| Memory | A stack frame per call, so memory grows with depth | Constant |
| Speed | Slower, because of call overhead | Faster |
| Risk | Stack overflow if the depth is large or the base case is wrong | Infinite loop if the condition is never met |
Use recursion where the problem is genuinely recursive: tree traversal, merge sort, quicksort, depth first search, and the Tower of Hanoi.
Parameter passing
- By value. A copy is passed. Changes inside the subroutine do not affect the original. Safer, but copying a large structure costs memory and time.
- By reference. The memory address is passed. Changes inside the subroutine do affect the original. Efficient for large structures, and it allows several values to be returned, but it makes side effects possible.
Scope and lifetime
Scope is where an identifier can be accessed. Lifetime is how long it exists in memory. A local variable is scoped to its subroutine and lives only while that subroutine runs. A global is accessible everywhere and persists for the whole program.
Prefer local. Global variables can be changed from anywhere, which makes a fault extremely hard to trace, and they prevent a subroutine from being reasoned about in isolation.
IDE features
Editor with syntax highlighting and auto complete, error diagnostics identifying the line and type, a run time environment, a translator, debugging tools including breakpoints, stepping and variable watches, refactoring tools, version control integration and automated test running.
Trace table trainer
Fill in a trace table row by row and have it marked as you type. This tool needs JavaScript, so turn it on to use it. Everything you need to answer the exam question is explained in the text above.
- Start: all the discs are on the first peg.
- Move the top n - 1 discs to the spare peg. That is the same problem, but smaller.
- Move the biggest disc to the target peg.
- Move the n - 1 discs on top of it, using the same method again.
Computational methods
Problem recognition
Some problems are amenable to computational solution and some are not. The question is whether the problem can be defined precisely, whether the necessary data is available, whether the rules can be stated explicitly, and whether the solution can be computed within acceptable time and resources.
Divide and conquer
Repeatedly split the problem into smaller instances of the same problem, solve those, and combine the results. Merge sort, quicksort and binary search all work this way. It reduces complexity substantially, typically from O(n2) to O(n log n).
Abstraction by generalisation
Grouping problems that share a structure so one solution serves all of them.
Backtracking
Explore a path, and when it proves not to lead to a solution, return to the last decision point and try a different option. Used for maze solving, constraint problems such as sudoku, and the eight queens problem.
Data mining
Searching very large datasets for patterns and relationships not previously known, such as products frequently bought together or early indicators of equipment failure.
Heuristics
A rule of thumb that produces a good enough solution quickly, where finding the optimal one would take unacceptably long. A satnav uses heuristics to avoid evaluating every possible route. A* uses a heuristic estimate of remaining distance to guide its search. The trade off is that the answer is not guaranteed to be optimal.
Performance modelling
Simulating a system mathematically to predict how it will behave under load, rather than building it and finding out. Far cheaper than testing the real system, and safe where the real system cannot be experimented on.
Pipelining
Dividing a process into stages so that different items occupy different stages simultaneously, as in a processor's instruction pipeline or a data processing pipeline.
Visualisation
Presenting data graphically so patterns invisible in raw figures become apparent. Human pattern recognition on a chart is far faster than reading a table of ten thousand rows.
- Divide and conquer: split, solve the small parts, combine.
- Backtracking: when a path fails, go back to the last choice and try another.
- Heuristics: a rule of thumb that gives a good answer quickly.
- Data mining: find patterns in a huge dataset.
- Performance modelling: predict behaviour from a model.
- Visualisation: charts show patterns a table of numbers hides.
Key terms you must be able to define
- Recursion
- A subroutine that calls itself, with a base case that stops the process.
- Base case
- The condition under which a recursive subroutine returns without calling itself again.
- Stack frame
- The record of parameters, local variables and return address created by each subroutine call.
- Stack overflow
- The error occurring when recursion becomes too deep for the available stack space.
- Pass by value
- Passing a copy, so changes inside the subroutine do not affect the original.
- Pass by reference
- Passing the address, so changes inside the subroutine do affect the original.
- Scope
- The region of a program in which an identifier can be accessed.
- Divide and conquer
- Repeatedly splitting a problem into smaller instances of itself and combining the results.
- Backtracking
- Returning to the last decision point when a path fails, and trying an alternative.
- Heuristic
- A rule of thumb producing a good enough solution quickly, without guaranteeing optimality.
- Performance modelling
- Simulating a system to predict its behaviour under load rather than building it.
- Visualisation
- Presenting data graphically so patterns become apparent to a human observer.
Flashcards
Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.
Reach the top grade on this topic
- Always identify the base case explicitly when writing or explaining recursion
- Compare recursion and iteration on memory as well as clarity, naming the stack frame
- Distinguish pass by value and pass by reference by effect on the original, not just mechanism
- Give a scenario for every computational method rather than a definition
- Explain a heuristic as trading optimality for speed, and say when that trade is acceptable
Mistakes that cost marks here
- Writing recursion with no base case, or with one the input never reaches.
- Saying recursion is more efficient. It is often clearer but uses more memory and is slower.
- Saying pass by reference passes the variable. It passes the address, which is why changes propagate.
- Defining a computational method without giving a scenario in which it applies.
- Saying a heuristic gives the best answer. It gives a good enough answer quickly.
Every recursive algorithm can be written iteratively and every iterative one recursively. The choice is about which one expresses the problem more clearly, and about whether you can afford the stack.
Knowledge check
Exam-style questions
Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.
- LA subroutine that calls itself
- LIt must include a base case that returns without recursing
- LAnd a general case moving towards the base case
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.
- LRecursion is a subroutine calling itself, iteration uses a loop
- LRecursion often expresses tree and divide and conquer problems more naturally
- LEach recursive call creates a stack frame, so memory use grows with depth
- LIteration uses constant memory and is generally faster
- LRecursion risks stack overflow where iteration risks an infinite loop
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.
- LBy value a copy of the data is passed to the subroutine
- LChanges made inside the subroutine do not affect the original
- LBy reference the memory address of the data is passed
- LChanges made inside the subroutine do affect the original, and no copy is made so it is efficient for large data
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.
- LA rule of thumb that produces an acceptable solution quickly
- LIt does not guarantee the optimal solution
- LIt is used where finding the optimal solution would take unacceptably long
- LGives a valid example such as route finding or the travelling salesman problem
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.
- LEach recursive call adds a stack frame to the call stack
- LWith 100000 calls the stack space available is exhausted
- LSuggests rewriting the function iteratively using a loop
- LAn iterative version uses constant memory regardless of n
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.