Its turtles all the way down RECURSION Lecture 8 CS2110 Spring 2019 Recursion: Look at Java Hypertext entry recursion. 2 Weve covered almost everything in Java! Just a few more things to introduce, which will be covered from time to time. Assignment A3 is about linked lists. Well spend 5-10 minutes on it in next Tuesdays lecture. A2 due tonight. Gries office hrs today, 1..3.

Note: For next week, the tutorial you have to watch is about loop invariants. Well introduce it in this lecture. Its important to master this material, because we use it a lot in later lectures. You know about method specifications and class invariants. Now comes the loop invariant. Next recitation: Loop invariants 3 In JavaHyperText, click on link Loop invariants in the horizontal navigation bar. Watch the videos on that page and the second page, 2. Practice on developing parts of loops. There will be a short quiz on Loop invariants and a problem set to do during recitation. We now introduce the topic. Next recitation: Loop invariants 4 // store in s the sum of the elements in array b. int k= 0; s= 0;

0 1 2 3 4 3 2 5 1 while (k < b.length) { s= s + b[k]; when done, s = 11 k= k+1; Why start with k = 0? } How do you know that s has the right value when the loop terminates? Why is b[k] added to s? Without giving meaning to variables, the only way you can tell this works is by executing it in your head, see what is does on a small array. A loop invariant will give that meaning. Next recitation: Loop invariants 5 int k= 0; s= 0; // invariant P: s = sum of b[0..k-1] This will be true before and after each iteration while (k < b.length) {

s= s + b[k]; 0 1 2 3 4 k= k+1; 3 2 5 1 } // R: s = sum of b[0..b.length-1] 0 k P: b s is sum of these ? b.length Loopy question 1: Does init truthify P? 6 int k= 0; s= 0; // invariant P: s = sum of b[0..k-1] This will be true before and after each iteration while (k < b.length) { k

s= s + b[k]; 0 1 2 3 4 k= k+1; 3 2 5 1 } // R: s = sum of b[0..b.length-1] s 0 0 k P: b s is sum of these ? b.length Loopy question 2: Is R true upon termination? 7 int k= 0; s= 0; // invariant P: s = sum of b[0..k-1] This will be true before and after each iteration while (k < b.length) {

k s= s + b[k]; 0 1 2 3 4 k= k+1; 3 2 5 1 } // R: s = sum of b[0..b.length-1] s 11 0 k P: b s is sum of these ? b.length Loopy question 3: Does repetend make progress toward termination? 8 int k= 0; s= 0; // invariant P: s = sum of b[0..k-1] This will be true before and after each iteration

while (k < b.length) { k s= s + b[k]; 0 1 2 3 4 k= k+1; 3 2 5 1 } // R: s = sum of b[0..b.length-1] s 5 0 k P: b s is sum of these ? b.length Loopy question 4: Does repetend keep invariant true? 9 int k= 0; s= 0; // invariant P: s = sum of b[0..k-1] This will be true before and

after each iteration while (k < b.length) { k s= s + b[k]; 0 1 2 3 4 k= k+1; 3 2 5 1 } // R: s = sum of b[0..b.length-1] s 5 0 k P: b s is sum of these ? b.length Loopy question 4: Does repetend keep invariant true? 10 int k= 0; s= 0;

// invariant P: s = sum of b[0..k-1] This will be true before and after each iteration while (k < b.length) { k s= s + b[k]; 0 1 2 3 4 k= k+1; 3 2 5 1 } // R: s = sum of b[0..b.length-1] s 10 0 k P: b s is sum of these ? b.length All four loopy questions checked. Loop is correct. 11

int k= 0; s= 0; // invariant P: s = sum of b[0..k-1] while (k < b.length) { s= s + b[k]; k= k+1; } // R: s = sum of b[0..b.length-1] 0 k P: b s is sum of these ? Use of invariant allows us to break loop (and init) into parts and handle them independently. Initialization? Look only at possible precondition of algorithm and loop invariant Termination? Look only at loop invariant, loop condition, postcondition.

To Understand Recursion 12 Recursion Real Life Examples 13 is , or , or Example: terrible horrible no-good very bad day Recursion Real Life Examples 14 is , or , or ancestor(p) is parent(p), or parent(ancestor(p)) great great great great great great great great great great great

great great grandmother. 0! = 1 n! = n * (n-1)! 1, 1, 2, 6, 24, 120, 720, 5050, 40320, 362880, 3628800, 39916800, 479001600 Sum the digits in a non-negative integer 15 /** = sum of digits in n. * Precondition: n >= 0 */ public static int sum(int n) { if (n < 10) return n; sum calls itself! // { n has at least two digits } // return first digit + sum of rest return n%10 + sum(n/10); } sum(7) = 7 sum(8703) = 3 + sum(870)

= 3 + 8 + sum(70) = 3 + 8 + 7 + sum(0) Two different questions, two different answers 16 1. How is it executed? (or, why does this even work?) 2. How do we understand recursive methods? (or, how do we write/develop recursive methods?) Stacks and Queues 17 stack grows top element 2nd element ... bottom

element first second last Americans wait in a line. The Brits wait in a queue ! Stack: list with (at least) two basic ops: * Push an element onto its top * Pop (remove) top element Last-In-First-Out (LIFO) Like a stack of trays in a cafeteria Queue: list with (at least) two basic ops: * Append an element * Remove first element First-In-First-Out (FIFO) Stack Frame 18

A frame contains information about a method call: At runtime Java maintains a a frame stack that contains frames for all method calls that are being executed but have not completed. local variables parameters return info Method call: push a frame for call on stack. Assign argument values to parameters. Execute method body. Use the frame for the call to reference local variables and parameters. End of method call: pop its frame from the stack; if it is a function leave the return value on top of stack. Memorize method call execution! 20 A frame for a call contains parameters, local variables, and other

information needed to properly execute a method call. To execute a method call: 1. push a frame for the call on the stack, 2. assign argument values to parameters, 3. execute method body, 4. pop frame for call from stack, and (for a function) push returned value on stack When executing method body look in frame for call for parameters and local variables. Frames for methods sum main method in

the system 21 public static int sum(int n) { if (n < 10) return n; return n%10 + sum(n/10); } public static void main( String[] args) { int r= sum(824); System.out.println(r); } Frame for method in the system that calls method main frame: frame: frame: n ___

return info r ___ args ___ return info ? return info Example: Sum the digits in a non-negative integer 22 public static int sum(int n) { if (n < 10) return n; return n%10 + sum(n/10); } public static void main( String[] args) { int r= sum(824); System.out.println(r); } Frame for method in the system

that calls method main: main is then called main system r ___ args ___ return info ? return info Memorize method call execution! 23 To execute a method call: 1. 2. 3. 4. push a frame for the call on the stack, assign argument values to parameters,

execute method body, pop frame for call from stack, and (for a function) push returned value on stack The following slides step through execution of a recursive call to demo execution of a method call. Here, we demo using: www.pythontutor.com/visualize.html Caution: the frame shows not ALL local variables but only those whose scope has been entered and not left. Example: Sum the digits in a non-negative integer 24 public static int sum(int n) { if (n < 10) return n; return n%10 + sum(n/10); } public static void main( String[] args) { int r= sum(824); System.out.println(r);

} Method main calls sum: main system 824 n ___ return info r ___ args ___ return info ? return info Example: Sum the digits in a non-negative integer 25 public static int sum(int n) { if (n < 10) return n; return n%10 + sum(n/10); }

public static void main( String[] args) { int r= sum(824); System.out.println(r); } n >= 10 sum calls sum: 82 n ___ return info 824 n ___ main system return info r ___ args ___ return info ? return info Example: Sum the digits in a non-negative

integer 26 public static int sum(int n) { if (n < 10) return n; return n%10 + sum(n/10); } public static void main( String[] args) { int r= sum(824); System.out.println(r); } n >= 10. sum calls sum: 8 n ___ return info 82 n ___ return info 824 n ___

main system return info r ___ args ___ return info ? return info Example: Sum the digits in a non-negative integer 27 public static int sum(int n) { if (n < 10) return n; return n%10 + sum(n/10); } public static void main( String[] args) { int r= sum(824); System.out.println(r); }

n8___ 8 return info 82 n ___ return info 824 n ___ main n < 10 sum stops: frame is popped system and n is put on stack: return info r ___ args ___ return info ? return info

Example: Sum the digits in a non-negative integer 28 public static int sum(int n) { if (n < 10) return n; return n%10 + sum(n/10); } public static void main( String[] args) { int r= sum(824); System.out.println(r); } 8 n82 ___ 10 return info main

Using return value 8 stack computes 2 + 8 = 10 pops frame from stack puts return value 10 on stack 824 n ___ return info r ___ args ___ return info ? return info Example: Sum the digits in a non-negative integer 29 public static int sum(int n) { if (n < 10) return n; return n%10 + sum(n/10); } public static void main(

String[] args) { int r= sum(824); System.out.println(r); } 10 main Using return value 10 stack computes 4 + 10 = 14 pops frame from stack puts return value 14 on stack n824 ___ 14 info return r ___ args ___ return info ? return info

Example: Sum the digits in a non-negative integer 30 public static int sum(int n) { if (n < 10) return n; return n%10 + sum(n/10); } public static void main( String[] args) { int r= sum(824); System.out.println(r); } Using return value 14 main stores 14 in r and removes 14 from stack main 14 r ___ 14 args __ return info

? return info Poll time! 31 Assume method main calls sumDigs(1837420) During this call, what is the maximum number of stack frames above (not including) main's stack frame? Questions about local variables 32 public static void m() { while () { int d= 5; } }

public static void m() { int d; while () { d= 5; } } In a call m() when is local variable d created and when is it destroyed? Which version of procedure m do you like better? Why? Two different questions, two different answers 33 1. How is it executed? (or, why does this even work?) Its not magic! Trace the codes execution using the method call algorithm, drawing the stack frames as you go. Use only to gain understanding / assurance that recursion works.

2. How do we understand recursive methods? (or, how do wedifferent write/develop recursive This requires a totally approach. methods?) Back to Real Life Examples 34 Easy to make math definition Factorial function: into a Java function! 0! = 1 public static int fact(int n) { n! = n * (n-1)! for n > 0if (n == 0) return 1; (e.g.: 4! = 4*3*2*1=24)

return n * fact(n-1); } Exponentiation: public static int exp(int b, int c) { b0 = 1 if (c == 0) return 1; bc = b * bc-1 for c > 0 return b * exp(b, c-1); } How to understand what a call does 35 Make a copy of the method spec, replacing the parameters of the method by the arguments sumDigs(654) sum of digits of n sum of digits of 654

spec says that the value of a call equals the sum of the digits of n /** = sum of the digits of n. * Precondition: n >= 0 */ public static int sumDigs(int n) { if (n < 10) return n; // n has at least two digits return n%10 + sumDigs(n/10); } Understanding a recursive method 36 Step 1. Have a precise spec! Step 2. Check that the method works in the base case(s): That is, cases where the parameter is small enough that the result can be computed simply and without recursive calls.

If n < 10 then n consists of a single digit. Looking at the spec we see that that digit is the required sum. /** = sum of the digits of n. * Precondition: n >= 0 */ public static int sumDigs(int n) { if (n < 10) return n; // n has at least two digits return n%10 + sumDigs(n/10); } Understanding a recursive method 37 /** = sum of the digits of n. * Precondition: n >= 0 */ Step 2. Check that the method public static int sumDigs(int n) { works in the base case(s).

if (n < 10) return n; // n has at least two digits Step 3. Look at the recursive return n%10 + sumDigs(n/10); case(s). In your mind replace } each recursive call by what it does according to the method spec and verify that the correct result is then obtained. return n%10 + sum(n/10); Step 1. Have a precise spec! return n%10 + (sum of digits of n/10); // e.g. n = 843 Understanding a recursive method 38 /** = sum of the digits of n. * Precondition: n >= 0 */

Step 2. Check that the method public static int sumDigs(int n) { works in the base case(s). if (n < 10) return n; // n has at least two digits Step 3. Look at the recursive return n%10 + sumDigs(n/10); case(s). In your mind replace } each recursive call by what it does acc. to the spec and verify correctness. Step 1. Have a precise spec! Step 4. (No infinite recursion) Make sure that the args of recursive calls are in some sense smaller than the pars of the method. n/10 < n, so it will get smaller until it has one digit Understanding a recursive method 39 Step 1. Have a precise spec!

Important! Cant do step 3 without precise spec. Step 2. Check that the method works in the base case(s). Step 3. Look at the recursive case(s). In your mind replace each recursive call by what it does according to the spec and verify correctness. Once you get the hang of it this is what makes recursion easy! This way of thinking is based on math induction which we dont cover in this course. Step 4. (No infinite recursion) Make sure that the args of recursive calls are in some sense smaller than the parameters of the method Writing a recursive method 40

Step 1. Have a precise spec! Step 2. Write the base case(s): Cases in which no recursive calls are needed. Generally for small values of the parameters. Step 3. Look at all other cases. See how to define these cases in terms of smaller problems of the same kind. Then implement those definitions using recursive calls for those smaller problems of the same kind. Done suitably, point 4 (about termination) is automatically satisfied. Step 4. (No infinite recursion) Make sure that the args of recursive calls are in some sense smaller than the parameters of the method Two different questions, two different answers 41 2. How do we understand recursive methods? (or, how do we write/develop recursive Step 1. Have a precise spec! methods?) Step 2. Check that the method works in the base case(s). Step 3. Look at the recursive case(s). In your mind replace each

recursive call by what it does according to the spec and verify correctness. Step 4. (No infinite recursion) Make sure that the args of recursive calls are in some sense smaller than the parameters of the method Examples of writing recursive functions 42 For the rest of the class we demo writing recursive functions using the approach outlined below. The java file we develop will be placed on the course webpage some time after the lecture. Step 1. Have a precise spec! Step 2. Write the base case(s). Step 3. Look at all other cases. See how to define these cases in terms of smaller problems of the same kind. Then implement those definitions using recursive calls for those smaller problems of the same kind. Step 4. Make sure recursive calls are smaller (no infinite recursion). Check palindrome-hood

43 A String palindrome is a String that reads the same backward and forward: isPal(racecar) true isPal(pumpkin) false A String with at least two characters is a palindrome if (0) its first and last characters are equal and (1) chars between first & last form a palindrome: have to be the same e.g. AMANAPLANACANALPANAMA have to be a palindrome A recursive definition! 44 A man a plan a caret a ban a myriad a sum a lac a liar a hoop a pint a catalpa a gas

an oil a bird a yell a vat a caw a pax a wag a tax a nay a ram a cap a yam a gay a tsar a wall a car a luger a ward a bin a woman a vassal a wolf a tuna a nit a pall a fret a watt a bay a daub a tan a cab a datum a gall a hat a fag a zap a say a jaw a lay a wet a gallop a tug a trot a trap a tram a torr a caper a top a tonk a toll a ball a fair a sax a minim a tenor a bass a passer a capital a rut an amen a ted a cabal a tang a sun an ass a maw a sag a jam a dam a sub a salt an axon a sail an ad a wadi a radian a room a rood a rip a tad a pariah a revel a reel a reed a pool a plug a pin a peek a parabola a dog a pat a cud a nu a fan a pal a rum a nod an eta a lag an eel a batik a mug a mot a nap a maxim a mood a leek a grub a gob a gel a drab a citadel a total a cedar a tap a gag a rat a manor a bar a gal a cola a pap a yaw a tab a raj a gab a nag a pagan a bag a jar a bat a way a papa a local a gar a baron a mat a rag a gap a tar a decal a tot a led a tic a bard a leg a bog a burg a keel a doom a mix a map an atom a gum a kit a baleen a gala a ten a don a mural a pan a faun a ducat a pagoda a lob a rap a keep a nip a gulp a loop a deer a leer a lever a hair a pad a tapir a door a moor an aid a raid a wad an alias an ox an atlas a bus a madam a jag a saw a mass an anus a gnat a lab a cadet an em a natural a tip a caress a pass a baronet a minimax a sari a fall a ballot a knot a pot a rep a carrot a mart a part a tort a gut a poll a gateway a law a jay a sap a zag a fat a hall a gamut a dab a can a tabu a day a batt a waterfall a patina a nut a flow a lass a van a mow a nib a draw a regular a call a war a stay a gam a yap a cam a ray an ax a tag a wax a paw a cat a valley a drib a lion a saga a plat a catnip a pooh a rail a calamus a dairyman a bater a canal Panama

Example: Is a string a palindrome? 45 /** = "s is a palindrome" */ public static boolean isPal(String s) { if (s.length() <= 1) Substring from return true; s[1] to s[n-1] // { s has at least 2 chars } int n= s.length()-1; return s.charAt(0) == s.charAt(n) && isPal(s.substring(1,n)); } The Fibonacci Function 46 Mathematical definition: fib(0) = 0 two base cases! fib(1) = 1 fib(n) = fib(n - 1) + fib(n - 2) n

2 Fibonacci sequence: 0 1 1 2 3 5 8 Fibonacci (Leonardo 13 /**= fibonacci(n). Pre: n >= 0 */ Pisano) 1170-1240? static int fib(int n) { if (n <= 1) return n; Statue in Pisa Italy // { 1 < n } Giovanni Paganucci return fib(n-1) + fib(n-2); 1863 } Example: Count the es in a string 47 /** = number of times c occurs in s */ public static int countEm(char c, String s) { if (s.length() == 0) return 0; substring s[1..] // { s has at least 1 character }

if (s.charAt(0) != c) return countEm(c, s.substring(1)); i.e. s[1] s(s.length()-1) // { first character of s is c} return 1 + countEm (c, s.substring(1)); } countEm(e, it is easy to see that this has many es) = 4 countEm(e, Mississippi) = 0