Understanding Recursion in Algorithms

Recursion Smaller. Stop.

Outline What is recursion Recursive algorithms with simple variables Recursion and arrays Recursion and complexity proof by induction

What is Recursion Recursion is a kind of Divide & Conquer Divide & Conquer Divide problem into smaller problems Solve the smaller problems Recursion Divide problem into smaller versions of itself Smallest version(s) can be solved directly

Coding Recursively Remember the two imperatives: SMALLER! when you call the method inside itself, one of the arguments has to be smaller than it was STOP! if the argument that gets smaller is very small (usually 0 or 1), then don t do the recursion

Recursive Countdown Print the numbers from N down to 1 recursive method (stop when N is zero) public static void countDownFrom(int n) { if (n > 0) { System.out.print(n + " "); countDownFrom(n - 1); } } to count down from 10: // STOP if n == 0! // SMALLER! print 10; count down from 9 . 10 9 8 7 6 5 4 3 2 1

Recursive Countdown Print the numbers from N down to 1 recursive method (stop when N is zero) public static void countDownFrom(int n) { if (n > 0) { System.out.print(n + " "); countDownFrom(n - 1); } } to count down from 9: // STOP if n == 0! // SMALLER! print 9; count down from 8 . 10 9 8 7 6 5 4 3 2 1

Recursive Countdown Print the numbers from N down to 1 recursive method (stop when N is zero) public static void countDownFrom(int n) { if (n > 0) { System.out.print(n + " "); countDownFrom(n - 1); } } to count down from 0: // STOP if n == 0! // SMALLER! (do nothing) 10 9 8 7 6 5 4 3 2 1

Recursive Functions Function defined in terms of itself one or more STOPs ( base case(s) ) one or more SMALLERs ( recursive case(s) ) 1 n*(n-1)! otherwise if n == 0 n! = 0 1 Fib(n 1)+Fib(n 2) if n == 0 if n == 1 otherwise Fib(n) =

The Factorial Method Product of numbers from N down to 1 recursive method public static int factorial(int n) { if (n > 0) { return n * factorial(n - 1); } else { return 1; } } // smaller // stop

Getting Smaller 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 1! 1! = 1 * 0! 0! = 1 Recursive Case Recursive Case Recursive Case Recursive Case Base Case 4 * 6 = 24 3 * 2 = 6 2 * 1 = 2 1 * 1 = 1 Base Case 1 n*(n-1)! otherwise if n == 0 n! = Recursive Case

Calling a Recursive Function Just like calling any other function System.out.println(factorial(5)); The function returns the factorial of what you give it because that s what it does it returns the factorial every time you call it including when you call it inside its definition

Towers of Hanoi // ----- s == start, f == finish, x == extra ----- // public static void hanoi(int n, char s, char f, char x) { if (n > 0) { // stop if n == 0 hanoi(n - 1, s, x, f); // smaller from start to extra System.out.println("Move a disk from " + s + " to " + f + "."); hanoi(n - 1, x, f, s); // smaller from extra to finish } }

Recursion with Arrays Simple recursion Values get smaller Hanoi(64) calls Hanoi(63) Hanoi(63) calls Hanoi(62) Recursion with arrays Array length gets smaller Look at less of the array

Example Array Recursion To Print an Array in reverse Base Case (Stop) If the array has length zero, do nothing Recursive Case (Smaller) First print the last element of the array Then print the rest of the array in reverse 6 100 3 -2 8 18 5 5 5 18 8 -2 3 100 6

Print Array in Reverse Give length of array to print, too reduce length by 1 until get to 0 NOTE: we re just pretendingit s smaller public static void printInReverse(int[] arr, int len) { if (len > 0) { System.out.print(arr[len - 1] + " "); printInReverse(arr, len - 1); // smaller array } } // stop if len == 0

Another Example To Find the Maximum Value in an Array Base Case if length is 1, the only element is the maximum Recursive Case Get the maximum from the rest of the array... ...& compare it to the last element Return the bigger 6 100 3 -2 8 18 5 100 5 100

Exercise Translate the (recursive) algorithm from the previous slide into Java Base Case if length is 1, the only element is the maximum Recursive Case Get the maximum from the rest of the array... ...& compare it to the last element Return the bigger Remember to use a pretend length

Working From Both Ends Sometimes we want to be able to shorten the array at either end Pass start and end points instead of length Done when lo > hi (for len==0), or lo == hi (for len==1) Sub-Array processing

Working From Both Ends Alternate way to find array maximum compare first and last elements drop the smaller out of range we re using stop when array has only one element left maximum is that one element 6 100 3 -2 8 18 5 100

Working From Both Ends Alternate way to find array maximum public static int maximum(int[] arr, int lo, int hi) { if (lo == hi) { return arr[lo]; } else if (arr[lo] > arr[hi]) { return maximum(arr, lo, hi - 1); } else { return maximum(arr, lo + 1, hi); } } // stop! // smaller // smaller

Array Splitting Sub-array processing can get rid of more than one element at a time Binary split is a common method do top half and bottom half separately combine to get answer 6 100 3 -2 8 18 5 100 18 100

Array Splitting Alternate way to find array maximum public static int maximum(int[] arr, int lo, int hi) { if (lo == hi) { return arr[lo]; } else { int mid = lo + (hi - lo) / 2; int maxLo = maximum(arr, lo, mid); // smaller! int maxHi = maximum(arr, mid+1, hi); // smaller! return Math.max(maxLo , maxHi); } } // stop!

Defensive Programming Consider finding the midpoint mid = lo + (hi lo) / 2; could just do (hi + lo) / 2 BUT what if the array is HUGE hi == 2,000,000,000; lo == 1,000,000,000 (hi + lo) / 2 == -647,483,648 (int overflow) lo + (hi lo) / 2 == 1,500,000,000 (no overflow) hi and lo both positive, so no underflow worry

Array Recursion Exercise Given an array and a number, find out if the number is in the array (contains method) NOTE: the array is unsorted Base Case(s) ? Recursive Case(s) ?

Recursive Algorithm Analysis Still in terms of size of problem size of n for factorial(n), fibonacci(n), size of array/linked structure in printInReverse, findMaximum, Base case probably just one operation Recursive case recursive count amount of work for n in terms of amount of work for n - 1

Work for printInReverse (Array) N is the length of the array (len) public static void printInReverse(int[] arr, int len) { if (len > 0) { System.out.print(arr[len - 1] + " "); printInReverse(arr, len - 1); } } if len == 0: compare len to 0: W(0) = 1 if len > 0: compare len to 0, print arr[len 1], call printInReverse with len-1: W(len) = 2 + W(len 1) // stop if len == 0 // smaller array

Recurrence Relation When W(n) defined in terms of W(n 1) or some other smaller value than n it s called a recurrence relation It s a recursive definition of W has a base case (n = 0 or n = 1 or ) has a recursive case public static int W(int n) { if (n == 0) return 1; else return 2 + W(n 1); }

Solving by Inspection Work for printInReverse: W(0) = 1 W(1) = 2 + W(0) = 3 W(2) = 2 + W(1) = 5 W(3) = 2 + W(2) = 7 W(4) = 2 + W(3) = 9 W(N) = 2 + W(N 1) (change) +2 +2 +2 +2 linear: factor of 2 = 2N + 1?

Solving by Inspection Table with N and Work for N (W) calculate change in work ( W) for each step N 0 1 2 3 4 5 N W 1 3 5 7 9 11 ? recurrence W W(0) + 2 W(1) + 2 W(2) + 2 W(3) + 2 W(4) + 2 2 2 2 2 2

Solving by Inspection: Linear Change in W will be a constant > 0 probably: W(N) = ( W)N + W(0) N 0 1 2 3 4 5 N W 1 3 5 7 9 11 recurrence W W(0) + 2 W(1) + 2 W(2) + 2 W(3) + 2 W(4) + 2 2 2 2 2 2 2N + 1

Solving by Inspection: Quadratic Add column for change in W ( W) constant W(N) = ( ( W)/2)N2+ N2 0 1 4 9 16 25 N 0 1 2 3 4 5 N W 1 3 7 13 21 31 recurrence W recurrence(2) ( W) W(0) + 2 W(1) + 4 W(2) + 6 W(3) + 8 W(4) + 10 W(N-1) + 2N 2 4 6 8 W(1) + 2 W(2) + 2 W(3) + 2 W(4) + 2 2 2 2 2 10 2N N2 + N + 1 N2 + ? + ?

Proving Your Formula You only looked at a few values will the formula you got work on all values? Can prove that a formula will work proof by induction Assume it works up to an arbitrary N 1 use recurrence relation to show it works for N proves it works up to any N

Proof by Induction (Linear) Suppose W(n) = 2n + 1 for n < N What is W(N)? W(N) = W(N 1) + 2 but N 1 < N, so: W(N 1) = 2(N 1) + 1 = 2N 2 +1 = 2N 1 W(N) = (2N 1) + 2 = 2N + 1 so W(N) also = 2N + 1 and that s for any N > 0 (recurrence relation)

Proof by Induction (Quadratic) Suppose W(n) = n2 + n + 1 for n < N What is W(N)? W(N) = W(N 1) + 2N but N 1 < N, so: W(N 1) = (N 1)2 + (N 1) + 1 = N2 N + 1 W(N) = (N2 N + 1) + 2N = N2 + N + 1 so W(N) also = N2 + N + 1 and that s for any N > 0 (recurrence relation)

Exercise Given recurrence reln W(N) = W(N-1) + 4, prove that W(N) = 4N + 5 Given W(N) = W(N-1) + 2N + 1, prove that W(N) = N2 + 2N

Analyzing Array Splitting Split array into two equal(ish) pieces easiest to analyze if N is a power of 2 1, 2, 4, 8, 16, or one less than that (if middle item removed) 0, 1, 3, 7, 15 makes exactly equal splits Need to factor in change in N

Analyzing Array Splitting Work when splitting exactly find maximum using array splitting 6 100 3 -2 8 18 5 35 W(8) W(4) W(4) W(8) = 2W(4) W(2) W(2) W(4) = 2 W(2) W(2N) = 2W(N)

Array Splitting public static int maximum(int[] arr, int lo, int hi) { if (lo == hi) { return arr[lo]; } else { int mid = lo + (hi - lo) / 2; int maxLo = maximum(arr, lo, mid); int maxHi = maximum(arr, mid+1, hi); return (maxLo > maxHi) ? maxLo : maxHi; // 1 comparison } } W(1) = 2 W(2) = 7 + 2W(1) = 7 + 2(2) = 11 W(4) = 7 + 2W(2) = 7 + 2(11) = 29 W(8) = 7 + 2W(4) = 7 + 2(29) = 65 W(16) = 7 + 2W(8) = 7 + 2(65) = 137 // 1 comparison // 1 array access // 3 math ops // 1 asgn + REC // 1 asgn + REC W / N + 9 / +1 +18 / +2 +36 / +4 +72 / +8 9N 7 9N 7 9N 7 9N 7

findMaximum by Splitting Split array into two (nearly equal) parts look at only powers of 2 even splits all the way down looks like W(N) = 9N 7 linear works for N <= 16 do induction on 2N instead of N+1 (later we ll do 2N+1)

Proof by Induction (Part 1) Assume W(n) = 9n 7 for n < 2N What s W(2N)? W(2N) = 7 + 2W(N) but N < 2N, so W(N) = 9N 7 so W(2N) = 7 + 2(9N 7) = 7 + 18N 14 = 18N 7 = 9(2N) 7 same formula works for all even N

Proof by Induction (Part 2) Assume W(n) = 9n 7 for n < 2N What s W(2N + 1)? W(2N + 1) = 7 + W(N) + W(N+1) but N < N+1 < 2N, so W(2N + 1) = 7 + (9N 7) + (9(N+1) 7) = 7 + 9N 7 + 9N + 9 7 = 18N + 9 7 = 9(2N+1) 7 same formula works for all odd N

Towers of Hanoi N = number of disks Work = number of moves W(0) = 0 W(1) = W(0) + 1 + W(0) = 1 W(2) = W(1) + 1 + W(1) = 3 W(3) = W(2) + 1 + W(2) = 7 W(4) = W(3) + 1 + W(3) = 15 W(5) = W(4) + 1 + W(4) = 31 (change) +1 +2 +4 +8 +16

Solve by Inspection Work doubles at each step of N sounds exponential compare work with 2N 2N = W(N) + 1 so work = 2N 1 exponential N 0 1 2 3 4 5 N W(N) 0 1 3 7 15 31 2N 1 2N 1 2 4 8 16 32 2N

Proof by Induction Assume W(n) = 2n 1 for n < N What s W(N)? W(N) = 1 + 2W(N 1) = 1 + 2(2N 1 1) = 1 + 2N 2 = 2N 1 formula works for all N

Exercise How much work is done by printInReverse for the linked structure? private void printInReverse(Node first) { if (first != null) { printInReverse(first.next); // smaller! System.out.println(first.data + " "); } } write recurrence relation solve order of magnitude // stop if list is empty!

Next Time Faster sorting methods