ALM_05_Recursion-1 Algorithmics & Logical Methods PDF

Algorithmics & Logical Methods Topic 5: Recursion Prof. Michael Madden Established Professor of Computer Science School of Computer Science, University of Galway M Madden A&LM (1) ...

Algorithmics & Logical Methods Topic 5: Recursion Prof. Michael Madden Established Professor of Computer Science School of Computer Science, University of Galway M Madden A&LM (1)  Learning Objectives – Topic 5 After completing this topic, you will be able to: 1. Explain what recursion is, and discuss the core features of a recursive function 2. Provide examples of classic recursive algorithms and present visualizations of their execution 3. Outline a recursive algorithm, develop it into pseudocode, and convert the pseudocode into a programming language code 4. Explain what tail recursion is and how to convert a tail recursive algorithm into a loop 5. Discuss the pros and cons of recursion M Madden A&LM (2)  Reminder: Call a Function from Another Function We have already seen functions that call other functions – Paving example: function calcArea(a,b) returns a*b – This was called from our main code block: BEGIN CALL GetInputs() main() SET wallArea = calcArea(wh,ww) SET brickArea = calcArea(bh,bw) [etc] END calcArea() FUNCTION calcArea(a, b): RETURN a * b ENDFUNCTION Note: A function is a type of module, in Java called a method M Madden A&LM (3)  Recursive Functions A recursive function is one that calls itself compute() A recursive function is another form of loop – Like other loops, recursive functions have to be carefully constructed so that they terminate correctly – Within the recursive function, there must be a condition to decide whether to call itself again – That condition must be based on values that change during calls to the loop, so that the condition to terminate will occur sometime M Madden A&LM (4)  Importance of Ensuring Loops Terminate Why did the programmer die in the shower? Because the shampoo label said: M Madden A&LM (5)  Why Use Recursive Functions? In computer science, some problems are more easily solved by using recursive methods – In this course, will see many examples of this. For example: – Traversing through directories of a file system. – Traversing through a tree of search results. – Some sorting algorithms recursively sort data. For now, we will focus on the basic structure of using recursive functions. M Madden A&LM (6)  Recursive Function Features Typically, recursive functions are used where: – You know the solution to 1 or more simple base cases – You can define more complex cases in terms of base cases – We will see examples such as Fibonacci Sequence A recursive function must have: 1. A test to stop or continue the recursion 2. A base case that terminates the recursion 3. Recursive call(s) that continue the recursion, making progress towards the solution, usually by tackling a simpler case M Madden A&LM (7)  Towers of Hanoi The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: – Only one disk can be moved at a time – You can only move the top disk in a stack – You can place a disk on an empty rod or on top of a larger disk, but not on top of a smaller disk. M Madden A&LM (8)  Towers of Hanoi The minimum number of moves required to solve a Tower of Hanoi puzzle is 2n - 1, where n is the number of disks – With three disks, the puzzle can be solved in seven moves 2^n-1 – With 10 disks, requires 1023 moves 4500 4000 Example of a problem with 3500 3000 exponential time complexity 2500 2000 1500 1000 500 0 M Madden 0 2 4 6 8 10 12 A&LM (9)  Towers of Hanoi: Recursive Solution Basic steps to shift N disks from A to C: – Shift top N-1 disks from A to B, using C. – Shift last disk from A to C. – Shift N-1 disks from B to C, using A. This gives us basis for a recursive algorithm to shift N disks: – Test if N is 1: Yes? To shift 1 disk, just move it (base case) No? Proceed as outlined above to shift N disks When we need to shift N-1 disks, apply this algorithm (Recursive case with slightly simpler version of the algorithm) M Madden A&LM (10)  Very Simple Recursive Algorithm This program simply counts from 0-2: BEGIN WRITE "Before count." CALL count(0) Before Count. WRITE "After count." 0 END 1 2 FUNCTION count(index) After count. WRITE index IF (index < 2) THEN This is where the recursion occurs. CALL count(index+1) ENDIF You can see that the count() ENDFUNCTION method calls itself. M Madden A&LM (11)  Very Simple Recursive Program public class Recursion { This program simply counts public static void main (String args[]) from 0-2: { System.out.println("Before count."); Before Count. count(0); 0 System.out.println("After count."); 1 } 2 public static void count (int index) After count. { System.out.println(index); if (index < 2) { This is where the recursion occurs. count(index+1); You can see that the count() } method calls itself. } } M Madden A&LM (12)  Visualizing Recursion To understand how recursion works, it helps to visualize what’s going on. To help visualize, we will use a common concept called the Stack. A stack operates like a container of trays in a cafeteria. It has two operations: – Push: you can push something onto the top of stack. – Pop: you can pop something off the top of the stack. Let’s see an example stack in action. M Madden A&LM (13)  Stacks The diagram below shows a stack over time. We perform two pushes and two pops. 8 2 2 2 Time: 0 Time 1: Time 2: Time 3: Time 4: Empty Stack Push “2” Push “8” Pop: Gets 8 Pop: Gets 2 M Madden A&LM (14)  Stacks and Methods When you run a program, the computer creates a stack for you. This is called the program stack. Each time you invoke a method, the method’s activation record is placed on top of the stack. When the method returns or exits, the method is popped off the stack. The diagram on the next slide shows a sample stack for a simple Java program. M Madden A&LM (15)  Stacks and Methods main() square() square() main() main() main() Time: 0 Time 1: Time 2: Time 3: Time 4: Empty Stack Push: main() Push: square() Pop: square() Pop: main() returns a value. returns a value. method exits. method exits. This is called an activation record or stack frame. Might also be visualized as growing downward. M Madden A&LM (16)  Very Simple Recursive Program: Visualise in Terms of Stacks public class Recursion { public static void main (String args[]) { System.out.println("Before count."); count(0); System.out.println("After count."); } public static void count (int index) { System.out.println(index); if (index < 2) { count(index+1); } } } M Madden A&LM (17)  Stacks and Recursion in Action count(2) count(1) count(1) count(0) count(0) count(0) main() main() main() main() … Time: 0 Time 1: Time 2: Time 3: Time 4: Times 5-8: Empty Stack Push: main() Push: count(0) Push: count(1) Push: count(2) Pop everything Inside count(2): Inside count(0): print (index); → 2 Inside count(1): print (index); → 0 if (index < 2) print (index); → 1 if (index < 2) count(index+1); if (index < 2) count(index+1); This condition is now false! count(index+1); Hence, recursion stops. As the program continues, we proceed to pop all methods off the stack. M Madden A&LM (18)  Original Program (Variation 1): Run it in Your Java Environment public class Recursion Recursion.java { public static void main (String args[]) { System.out.println("Before count."); count(0); System.out.println("After count."); } public static void count (int index) { System.out.println(index); if (index < 2) { count(index+1); } } } M Madden A&LM (19)  Program Variation 2: What Will This Do Differently? public class RecursionVar2 Modify { public static void main (String args[]) Recursion.java { yourself System.out.println("Before count."); count(0); System.out.println("After count."); } public static void count (int index) { if (index < 2) { count(index+1); Note that the print statement } has been moved to the end System.out.println(index); } of the method. } M Madden A&LM (20)  Program Variation 3: What About This One? public class RecursionVar3 Modify { public static void main (String args[]) Recursion.java { yourself System.out.println("Before count."); count(3); Different starting value System.out.println("After count."); } public static void count (int index) { System.out.println(index); if (index > 2) { Changed operator to > count(index+1); } } } M Madden A&LM (21)  Program Variation 3: Not working towards base case Reminder: a recursive function must have: 1. A test to stop or continue the recursion 2. A base case that terminates the recursion 3. Recursive call(s) that continue the recursion, making progress towards the solution, usually by tackling a simpler case In the Program Variation 3, we do not work towards our solution – Each call moves further away from the condition in the base case – This cases infinite recursion – The program keeps running until it runs out of memory for the stack: this is called a Stack Overflow Error M Madden A&LM (22)  Recursion Example 2: Examine to determine output, then test by running public class Recursion2 Recursion2.java { public static void main (String args[]) { upAndDown(1); } public static void upAndDown(int n) { System.out.println("Level: " + n); if (n < 4){ upAndDown(n+1); Recursion occurs here } System.out.println("LEVEL: " + n); } } M Madden A&LM (23)  Classic Examples of Recursion and Properties of Recursive Functions M Madden A&LM (24)  Factorials Computing factorials are a classic problem for examining recursion. A factorial is defined as follows: n! = n * (n-1) * (n-2) …. * 1 where n > 1 Also: 1! = 1, 0! = 1, factorials are only defined for non-negative integers For example: 1! = 1 2! = 2 * 1 = 2 If you study this table, 3! = 3 * 2 * 1 = 6 you will see a pattern. 4! = 4 * 3 * 2 * 1 = 24 5! = 5 * 4 * 3 * 2 * 1 = 120 M Madden A&LM (25)  Seeing the Pattern At first, it might be difficult to see the pattern in the factorial Once you see the pattern, you can apply this pattern to create a recursive solution to the problem Divide a problem up into: – What we know (call this the base case) – Making progress towards the base Each step resembles original problem The method launches a new copy of itself (recursion step) to make the progress. M Madden A&LM (26)  Factorials Computing factorials are a classic problem for examining recursion. A factorial is defined as follows: n! = n * (n-1) * (n-2) …. * 1 where n > 1 Also: 1! = 1, 0! = 1, factorials are only defined for non-negative integers For example: The pattern is as follows: 1! = 1 The factorial of any number (n) is 2! = 2 * 1 = 2 n multiplied by the factorial of (n-1). 3! = 3 * 2 * 1 = 6 4! = 4 * 3 * 2 * 1 = 24 For example: 5! = 5 * 4 * 3 * 2 * 1 = 120 5! = 5 * 4! M Madden A&LM (27)  Factorials: Recursive Algorithm Pattern we just observed: From this we can define a n! = n * (n-1)! recursive algorithm: We also have base cases: fac(n): 0! = 1 if (n < 0) Error 1! = 1 if (n == 0) return 1 n must be a non-negative integer Base case if (n == 1) return 1 return n * fac(n-1) Making progress M Madden A&LM (28)  Factorials: Recursive Algorithm in Pseudocode Pseudocode Version: fac(n): FUNCTION Fac(n): if (n < 0) Error IF (n < 0) THEN WRITE "Error" if (n == 0) return 1 STOP if (n == 1) return 1 ENDIF return n * fac(n-1) IF (n == 0) OR (n == 1) THEN Base case RETURN 1 ENDIF RETURN (n * Fac(n-1)) Making progress ENDFUNCTION M Madden A&LM (29)  Factorials: Recursive Algorithm in Java public class Factorial { public static void main (String args[]) { Factorial.java int val = 3; int facval = factorial(val); System.out.println("The factorial of " + val + " is " + facval); } public static int factorial(int n) { if (n < 0) { System.out.println("ERROR: undefined for negative values " + n); return -999; // or System.exit(0); } if (n == 0 || n == 1) { return 1; } return (n * factorial(n-1)); } } M Madden A&LM (30)  Finding the Factorial of 3: Program Stack fact(1) 1 fact(2) fact(2) fact(2) 2 fact(3) fact(3) fact(3) fact(3) fact(3) 6 main() main() main() main() main() main() Time 2: Time 3: Time 4: Time 5: Time 6: Time 7: Push: fact(3) Push: fact(2) Push: fact(1) Pop: fact(1) Pop: fact(2) Pop: fact(3) returns 1. returns 2. returns 6. Inside factorial(3): Inside factorial(2): Inside factorial(1): if (number