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 output ( OUTPUT num ). The variable count will keep track of how many times the while loop has repeated. The trace table shows how this algorithm would run if the user entered an input of 16. Algorithm Trace table num count num < 500 OUTPUT 16 0 True 32 1 True 64 2 True 128 3 True 256 4 True 512 5 False 512 5 1.2 Exercises Complete the trace tables for the following algorithms. Algorithm 1 Trace table num OUTPUT 4

VJC/H2Computing/9569 Algorithm 2 Trace table number factorial number > 2 OUTPUT Algorithm 3 Trace table 5

VJC/H2Computing/9569 i digit code OUTPUT 2 Recursion The process in which a function calls itself directly or indirectly is known as recursion. The corresponding function is called a recursive function. Generally, a recursive function has these features: 1. It is defined in terms of itself. 2. It calls itself with one or more similar but smaller problems. 3. It can repeat itself until a base case or terminating case is reached. A base case or terminating condition is a condition that determines when the recursion should stop. It is the smaller problem that is simple enough to be solved easily and does not require further recursion. Any iteration can possibly be rewritten into a recursive function and vice versa. 2.1 Recursion without return value Let’s look at a countdown() function using while loop. It takes in a parameter n, which is the starting number to count down to 1. Can this function be converted into a recursive function? YES! How do we convert the countdown function into a recursive function? 6

VJC/H2Computing/9569 7

VJC/H2Computing/9569 Analysis steps: ● What are the common actions in each loop? (Hint: check the loop statements) ● What is the base case (or terminating case)? ● What does it do when it is the base/terminating case? Analysis result: ● In each iteration, it prints out current n value. ● The base case is when n = 0 . ● If base case is True , it prints Done . Thus, ● In the recursive function, it checks for the base case. ● Once the base case is true, it prints Done, else it prints current n value and recurses (calls the same function again) Let’s convert the countdown() function into a recursive function countdown_r(). How do you visualise the above recursive function execution? 1. Trace table Call number Procedure call n n == 0 OUTPUT 1 countdown_r(3) 3 False 3 2 countdown_r(2) 2 False 2 3 countdown_r(1) 1 False 1 4 countdown_r(0) 0 True "Done " 2. Trace tree 8

VJC/H2Computing/9569 Let’s modify the countdown() function into a recursive function count up function countup_r(). By switching the code on line 5 and 6, we can totally change a count down to a count up as the order of execution has been switched. Instead of printing n followed by calling the function, the program recursively calls the function until it reaches the base case then it starts the printing. Let’s visualise the execution order of the countup_r function. 9

VJC/H2Computing/9569 1. Trace table Call number Procedure call n n == 0 OUTPUT 1 countup_r(3) 3 False 2 countup_r(2) 2 False 3 countup_r(1) 1 False 4 countup_r(0) 0 True "Done " 3 countup_r(1) 1 False 1 2 countup_r(2) 2 False 2 1 countup_r(3) 3 False 3 2. Trace tree 2.2 Recursion with return value In the above count-down and count-up examples, the recursion function does not return any value. It is common for recursion functions to return value back to the calling function. Let’s look at a recursion function with return value. Factorial The factorial value of an explicit number n is typically represented as n! , and 𝐹 𝑛 = 𝑛 ∗ 𝐹 𝑛 − 1 . n! = n * (n-1) * (n-2) * . . . * 1 n! = n * (n-1)! 10