Table of Contents
I. Software Systems and Methodology – 40%
B. Program control and structure
1. Iteration and recursion
a. Definition: Iteration is the process of performing the same actions multiple times. Loops are the best examples of iteration.
b. Definition: Any function that calls itself is recursive. It looks a lot like iteration, but iteration always has a way to end (i.e. a conditional check). Poorly constructed recursive functions could potentially exclude a conditional check of some sort.
c. We use loops or iteration to perform the same sequence of actions repeatedly.
d. There are 3 basic loops in C and Pascal: fixed repetition, pretest, and posttest.
i. Fixed repetition uses the form for <assignment> to <value> do <statement>. The statement is the set of actions that the program repeats. The for/to section controls the loop. Since this loop does not do any conditional check, it will repeat a fixed number of times.
ii. The pretest style loop will perform a conditional check before it executes the statement. Pascal uses the form while <conditional check> do <statement>.
iii. The posttest loop performs the conditional check at the end of the statement. This has a major implication: this loop will always perform one iteration. The Pascal form of the posttest loop is repeat <statement> until <conditional check>.
e. Recursive functions are functions that call themselves. We use them because they are often easy to code because they translate very easily from a recursive mathematical function. There are four rules to remember when implementing recursive functions. 1) Always have a base case that is solved without calling itself, 2) Progress towards that base case, 3) Have faith (believe that the recursive call will work), and 4) avoid duplication of work – do not solve the same instance of a case more than once. If you leave out the base case, then you will have problems. If you break rule 4, then you will probably have an exponentially time complex algorithm. Remember that loops are sometimes more efficient and easier than recursive functions.
f. Each call to a recursive function uses a process called an activation record. The major issue with having the same function called more than once is that each instance of the function needs to keep its local variables separate from the other calls. When the function is called, the activation record details certain conditions for the call. When the function ends, the computer needs to know the memory location to execute next (the return address). In a stack-based programming language, the computer keeps track of recursive calls by placing each activation record on a stack. More specifically, the stack holds pointers to each of the activation records (which hold the information about how to access the function and related non-local variables and types).
g. Since recursive functions require activation records and other resources, they are usually slower than the equivalent iteration.
