Structure of Procedural Programs
Statement - the simplest part of programming logic. For example, "if doughnuts > 5" is an if statement.
Subroutine - a small program to complete a specific task, packaged as a unit.
Procedure - a type of subroutine which can output more than one value.
Function - a type of subroutine which can only output one value.
Parameter (argument) - data which is passed from the main program to a subroutine.
Sequence - a type of programming construct which involves following a sequence of instructions.
Selection - a type of programming construct which involves choosing which out of several sequences to follow (or to follow none, and terminate the program).
Iteration (repetition) - a type of programming construct which involves repeating a section of a program until a condition is met. The section might not be executed if the condition is already met.
Loop - where code is executed multiple times. Unless loops have an exit criteria, the program could get stuck in an infinite loop.
The 3 Constructs - Sequence, Selection, and Iteration (2.2.b)
There are three key ways to construct a program: Sequence, Selection, and Iteration. Sequence is the simplest - a list of instructions are simply executed in order, one line at a time.
Selection are where there are several "paths" which the program could be run down. Depending on various conditions, the program will run through one of the paths, or will stop running.
The program repeats a sequence of instructions until a certain condition is met. If the condition is already met, the sequence may not be iterated. If the condition is never met, then the program will be stuck in an infinite loop, and it could crash the computer.
Selection statements can be nested within iteration statements (and vice versa). For example:
WHILE SUGAR < 100: IF APPLES >= 1: EAT(APPLE) SUGAR += 5 ELSE IF CHOCOLATE >= 1: EAT(CHOCOLATE) SUGAR += 10
You might also be given some incorrectly nested code, and be asked to "debug" it.
When a subroutine is called, the code in the subroutine is executed, and then the control is passed back to the main program. Typically questions are either related to functions and procedures, or involve "tracing" through a subroutine for a given set of inputs (showing working at each line).
Recursion is simply where a subroutine calls itself. A large number of problems are most simply solved by using recursion. For example, the simplest way to find 1024! is to calculate 1024 x 1023!. This is how an algorithm using recursion would calculate factorials. There must always be a condition to halt the recursion, for example 1! = 1, otherwise the program will get "stuck" in an infinite loop.
def factorial(n): if n == 1: return 1 else: return n * factorial(n-1)
Download the python function. Use factorial(n) to calculate a factorial, where n is an integer.
You could be asked to "trace" a recursive subroutine. This is really simple - it just means that you need to follow it through, writing down any calculations, and the values of any variables as they change, as well as when the subroutine calls itself.
Iteration vs Recursion (2.2.i)
Iteration - a loop is used to repeat instructions. There is a stopping condition which decides when to stop looping. A variable needs to be used to track progress towards the stopping condition. As there is only one function call, there is only one set of variables, so an iterative algorithm will use less memory and be more efficient. However, using variables to keep track means that those variables may need to be initialised before the loops start, and they may make the code harder to understand.
Recursion - the function calls itself to repeat instructions. The stopping condition prevents the function from calling itself, and terminates the function. The arguments used must eventually lead to the stopping condition. As there are many function calls, each with their own set of variables, more memory is used during execution. However, the code is simpler to understand, and similar to the way a human would describe the algorithm.
In a nutshell, iteration is is more efficient, and recursion is more readable.