Understanding Recursion for Efficient Problem Solving

Recursion

Canonical example: factorial Recursion When a method calls itself Classical example the factorial function n! = 1 2 3 (n-1) n Recursive definition = 1 if n 0 = ( ) f n ( ) 1 n f n else

Example I using recursion: Sum of values from 1 to N Problem computing the sum of all the numbers between 1 and N This problem can be recursively defined as: 1 2 N N N = i = i = i = + = + + 1 i N i N N i 1 1 1 3 N = i = + + + 1 2 N N N i 1

Example I using recursion: Sum of values from 1 to N (ctd) // This method returns the sum of 1 to num // Refer to SumApp project public int sum (int num) { int result; if (num == 1) result = 1; else result = num + sum (n-1); return result; }

Example I using recursion: Sum of values from 1 to N (ctd) result = 6 main sum(3) result = 3 sum sum(2) result = 1 sum sum(1) sum

Content of recursive definition Base case (s) Values of the input variables for which no recursive calls are performed There should be at least one base case Every chain of recursive calls must Eventually reach a base case Recursive calls Calls to the current method Defined in such a way that It makes progress towards a base case

Example II using recursion: Factorial Factorial of a positive integer n, written n! is the product n (n 1) (n 2) 1 with 1! equal to 1 and 0! defined to be 1 The factorial of integer number can be calculated iteratively (non-recursively) using a for statement as follows: factorial = 1; for(int counter = number; counter >= 1; counter-- ) factorial *= counter; Recursive declaration of the factorial method is arrived at by observing the following relationship: n! = n (n 1)!

Example II using recursion: Factorial (cont d) long should be used so that the program can calculate factorials greater than 12! Package java.math provides classes BigInteger and BigDecimal explicitly for high precision calculations not supported by primitive types. Refer to FactorialApp project

Example II using recursion: Factorial (cont d) BigInteger method compareTo compares the BigInteger that calls the method to the method s BigInteger argument. Returns -1 if the BigInteger that calls the method is less than the argument, 0 if they are equal or 1 if the BigInteger that calls the method is greater than the argument. BigInteger constant ONE represents the integer value 1. ZERO represents the integer value 0.

Example III using recursion: Fibonacci Series The Fibonacci series, begins with 0 and 1 and has the property that each subsequent Fibonacci number is the sum of the previous two. 0, 1, 1, 2, 3, 5, 8, 13, 21, The ratio of successive Fibonacci numbers converges to a constant value of 1.618 , called the golden ratio or the golden mean. The Fibonacci series may be defined recursively: fibonacci(0) = 0 fibonacci(1) = 1 fibonacci(n) = fibonacci(n 1) + fibonacci(n 2)

Example III using recursion: Fibonacci Series Two base cases for Fibonacci method fibonacci(0) is defined to be 0 fibonacci(1) to be 1 Fibonacci numbers tend to become large quickly. We use type BigInteger as the the return type of The fibonacci method BigInteger methods multiply and subtract implement multiplication and subtraction. Refer to FibonacciApp project

Visualizing Recursion for Factorial Recursion trace Example recursion trace: return 4*6 = 24 final answer A box for each recursive call call recursiveFactorial(4) return 3*2 = 6 call An arrow from each caller to callee recursiveFactorial(3) return 2*1 = 2 call recursiveFactorial(2) return 1*1 = 1 call An arrow from each callee to caller showing return value recursiveFactorial(1) return 1 call recursiveFactorial(0)

Example IV using recursion: Binary Search A binary search Assumes the list of items in the search pool is sorted Eliminates a large part of search pool with 1 comparison Examines the middle element of the list If it matches the target, the search is over Otherwise, only one half of the remaining elements Need to be searched Then examines the middle element of remaining pool Eventually, the target is found or data is exhausted

Example IV using recursion: Binary Search (cont d) Example: Search a sorted array for a given value end: index of 1st element in search pool start: index of 1st element in search pool middle A BS(A, key, start, end) Look for key in the array A where elements are sorted according to ascending order A method that calls itself with a smaller input set

Binary search recursion: pseudo-code // Refer to BinarySearchApp project Boolean BS(A, key, start, end) mid = (start+end)/2 if(A[mid] == key) return true else if(end <= start) else return false if (A[mid] > key) return BS(A, key, start, mid-1) else return BS(A, key, mid+1, end)

Example V using recursion: Towers of Hanoi Given A platform with three pegs sticking out of it Each peg is a stack that can accommodate n disks Puzzle Move all disks from peg a to peg c, one disk at a time So that we never place a larger disk on top of smaller one Refer to TowersOfHanoiApp project

Towers of Hanoi Original Configuration Move 1 Move 2 Move 3

Towers of Hanoi Move 4 Move 5 Move 6 Move 7 (done)