1Chapter 13RecursionTopics• Simple Recursion• Recursion with a Return Value• Binary Search Revisited• Recursion Versus IterationSimple Recursion• When solving a problem using recursion, the idea is to transform a big problem into a smaller, similar problem.• Eventually, as this process repeats itself and the size of the problem is reduced at each step, we will arrive at a very small, easy-to-solve problem.• That easy-to-solve problem is called the base case.• The formula that reduces the size of a problem is called the general case. Recursive Methods• A recursive method calls itself, i.e. in the body of the method, there is a call to the method itself. • The arguments passed to the recursive call are smaller in value than the original arguments.2Simple Recursion• When designing a recursive solution for a problem, we need to do two things:– Define the base case.– Define the rule for the general case.Printing “Hello World” n Times Using Recursion• In order to print “Hello World” n times (n is greater than 0), we can do the following:– Print “Hello World”– Print “Hello World” (n – 1) times• This is the general case.• We have reduced the size of the problem from size n to size (n – 1).Printing “Hello World” n Times Using Recursion• Printing “Hello World” (n – 1) times will be done by – Printing “Hello World” – Printing “Hello World” (n – 2) times• … and so on • Eventually, we will arrive at printing “Hello World” 0 times: that is easy to solve; we do nothing. That is the base case.Coding the Recursive Methodpublic static void printHelloWorldNTimes( int n ){ if ( n > 0 ){System.out.println( “Hello World” );printHelloWorldNTimes( n – 1 );}// if n is 0 or less, do nothing}• See Example 13.1 RecursiveHelloWorld.java3Recursion with a Return Value• A recursive method is a method; as such, it can be a value-returning method.• In a value-returning method, the return statement can include a call to another value-returning method.• For example,public int multiplyAbsoluteValueBy3( int n ){return ( 3 * Math.abs( n ) );}Recursion with a Return Value• In a recursive value-returning method, the returnstatement can include a call to the method itself.• The return value of a recursive value-returning method often consists of an expression that includes a call to the method itself:return ( expression including a recursive call to the method );Factorial• The factorial of a positive number is defined as factorial( n ) = n! = n * ( n – 1 ) * ( n – 2 ) * … 3 * 2 * 1– By convention, factorial( 0 ) = 0! = 1– The factorial of a negative number is not defined.• Can we find a relationship between the problem at hand and a smaller, similar problem?Factorialfactorial( n ) = n! = n * ( n – 1 ) * ( n – 2 ) * … 3 * 2 * 1factorial( n - 1 ) = ( n – 1 )! = ( n – 1 ) * ( n – 2 ) * … 3 * 2 * 1• So we can writefactorial( n ) = n * factorial( n – 1 )• That formula defines the general case.4Factorialfactorial( n ) = n * factorial( n – 1 )• At each step, the size of the problem is reduced by 1: we progress from a problem of size n to a problem of size (n – 1)• A call to factorial( n ) will generate a call to factorial( n – 1 ), which in turn will generate a call to factorial( n – 2 ), ….• Eventually, a call to factorial( 0 ) will be generated; this is our easy-to-solve problem. We know that factorial( 0 ) = 1. That is the base case.Code for a Recursive Factorial Methodpublic static int factorial( int n ){ if ( n <= 0 ) // base casereturn 1;else // general casereturn ( n * factorial( n – 1 ) );}• See Example 13.2 RecursiveFactorial.javaCommon ErrorTrapWhen coding a recursive method, failure to code the base case will result in a run-time error.If the base case is not coded, when the method is called, the recursive calls keep being made because the base case is never reached.This eventually generates a StackOverflowError.Recursion Versus Iteration• A recursive method is implemented using decision constructs (if/else statements) and calls itself.• An iterative method is implemented with looping constructs (while or for statements) and repeatedly executes the loop.• Printing “Hello World” n times and calculating a factorial can easily be coded using iteration.• Other problems, such as the Towers of Hanoi and Binary Search, are more easily coded using recursion.5Recursion Versus Iteration• Considerations when deciding to use recursion or iteration include:– Efficiency of the method at execution time: often, recursion is slower due to overhead associated with method calls.– Readability and maintenance: often, a recursive formulation is easier to read and understand than its iterative equivalent.Back UpSlidesRecursive Binary Search• Our Recursive Binary Search will implement a Binary Search using recursion.• Review: A Binary Search searches a sorted array for a search key value.– If the search key is found, we return the index of the element with that value.– If the search key is not found, we return -1.The Binary Search Algorithm• We begin by comparing the middle element of the array with the search key. • If they are equal, we found the search key andreturn the index of the middle element.• That is a base case.6Binary Search (con't)• If the middle element's value is greater than the search key, then the search key cannot be found in elements with higher array indexes. So, wecontinue our search in the left half of the array. • If the middle element's value is less than the search key, then the search key cannot be found in elements with lower array indexes lower. So, wecontinue our search in the right half of the array. The Binary Search Algorithm (con't)• Searching the left or right subarray is made via a recursive call to our Binary Search method. We pass the subarray to search as an argument. Since the subarray is smaller than the original array, we have progressed from a bigger problem to a smaller problem. That is our general case.• If the subarray to search is empty, we will not find our search key in the subarray, and we return –1. That is another base case.Example of a Recursive Binary Search• For example, we will search for the value 7 in this sorted array:• To begin, we find the index of the center element, which is 8, and we compare our search key (7) with the value 45.Recursive Binary Search