VJC Chapter 10 Recursion

VJC/H2Computing/9569 Chapter 10: Recursion Contents 1 Trace tables 1.1 Examples 1.2 Exercises 2 Recursion 2.1 Recursion without return value 2.2 Recursion with return value 2.3 Using stacks to store return addresses 2.4 Benefits and drawbacks of recursion Syllabus Learning Outcomes 2.2 Programming Elements and Constructs Use programming language elements and constructs to write recursive and non-recursive programs to solve a variety of problems. 2.2.5 Understand the concept of recursion. 2.2.6 Trace the steps and list the results of recursive and non-recursive programs. 2.2.7 Understand the use of stacks in recursive programming. 1

VJC/H2Computing/9569 1 Trace tables Using trace tables is a technique used to test an algorithm and predict step by step how the computer will run the algorithm. Trace tables are tables that consist of columns. Each column can represent a variable, a condition, or an output. Not every variable, condition or output in an algorithm needs a column in a trace table. The purpose of the table is that we can run through an algorithm and simulate what a computer would do if the program were to execute. We complete the table to show how the variables change, what the conditions would resolve to, and/or what outputs would be displayed. There are two main reasons that trace tables are used. The first is to determine what an algorithm does by running through it to see what happens as the algorithm runs. The second is to test the logic of an algorithm if there are errors that are not easily spotted. 1.1 Examples A trace table can be used to track the values of variables as they change from line to line while the program is running. 2

VJC/H2Computing/9569 "Line" may not always be a column in a trace table. The above trace table can be drawn with columns consisting only the variables and output. The following examples show some basic algorithms and their trace tables. Example 1 The purpose of the algorithm in this example is to swap the values of x and y. Algorithm Trace table x y temp 3 4 3 4 3 Example 2 This algorithm includes a conditional statement - IF/ELSE. Algorithm Trace table 1 code = 61 2 IF code MOD 2 == 0 THEN code = code * 3 3 ELSE code = code * 2 4 ENDIF 5 OUTPUT code code code MOD 2 == 0 OUTPUT 61 False 122 122 3

VJC/H2Computing/9569 Example 3 The algorithm below contains 2 variables ( num , count ), 1 condition ( num < 500 ) and 1