3: Methods and Recursion

What We Will Cover Announcements Illuminations 3.1: Methods 3.1.1: About Methods 3.1.2: Mathematical Methods 3.1.3: Defining Methods 3.1.4: Passing Values 3.1.5: Returning a Value 3.1.6: Local Variables and Scope 3.1.7: Overloading Methods Exercise 3.1 3.2: Recursion 3.2.1: About Recursion 3.2.2: Implementing Recursive Methods 3.2.3: Factorial: Classic Recursion 3.2.4: Recursion and the Call Stack 3.2.5: Recursion Versus Iteration 3.2.6: Iteration to Recursion 3.2.7: Summary Exercise 3.2 Wrap Up Due Next: A3: Factorials of Interest (3/2/05) Illuminations Review of Assignment A2: Decimal Palindromes (2/23/05) How did you handle isolating single digits? How did you handle rounding errors? Did your program work with the tests? Viewing WebCT Assignment Results WebCT ^ top 3.1: Methods Objectives At the end of the lesson the student will be able to: Create and call methods Pass values to methods Overload methods Exit methods ^ top 3.1.1: About Methods Method -- a subprogram (function, procedure or subroutine) that executes a block of code when called. Methods take parameters and return values. Why Methods? Methods allow grouping of related code that performs specific task Aids in structuring code Makes program development more manageable Makes it easier to reuse sections of code Rule of thumb: If you repeat the same sequence of 3 or more lines more than once, you should create a method for the task performed. Using Methods Methods are invoked by a method call Arguments are used to pass information to methods double result = square(5); Parameters are the variable that contains the arguments passed to a method static double square(double x) { return x * x; } Methods return a result to calling method (caller) Similar to a boss (caller) asking a worker (called method) to complete a task ^ top 3.1.2: Mathematical Methods Java has many methods in the API libraries One example is the Math class Provides many methods for mathematical operations not provided by operators Name Description Example Result abs absolute value Math.abs(-3.9) Math.abs(3.9) 3.9 3.9 exp exponent Math.exp(1.0) 2.718... log natural log Math.log(10.0) 2.40... pow powers Math.pow(2.0, 3.0) 8.0 sqrt square root Math.sqrt(4.0) 2.0 In addition, includes three similar methods: round, floor, and ceil Name Description Example Result ceil ceiling: round up Math.ceil(3.3) Math.ceil(3.7) 4.0 4.0 floor floor: round down Math.floor(3.3) Math.floor(3.7) 3.0 3.0 round round: round off Math.round(3.3) Math.round(3.7) 3.0 4.0 All three return whole numbers, although they are of type double Method Math.random Random numbers are a series of numbers whose order cannot be predicted Many computational problems need use of random numbers Hard to find truly random numbers, even in real life Dice are never perfect Cards are never shuffled completely randomly Computers can only handle numbers within a finite range and limited precision Best that can be done in most cases is generate psuedorandom numbers Sufficiently random for the task at hand Math.random produces series of psuedorandom numbers Range is 0.0 up to, but not including, 1.0 Returns a double-precision value Example Use of Random Numbers Since the range of Math.random is between 0.0 and 1.0, you need to scale it for your application Also may need to shift the starting point of the numbers General form for producing integer random numbers for an application: shiftingValue + (int) (Math.random() * scalingFactor); For example, to simulate a single 6-sided die with random numbers: int die = 1 + (int) (Math.random() * 6); System.out.println("You rolled a " + die); ^ top 3.1.3: Defining Methods Programmers can write customized methods Syntax: returnValueType methodName(parameterList) { .... } Begins with the data type of the value that will be returned Can be any primitive type (char, int, double, etc.) or class (String, etc.) When no values are returned, use the special type: void After specifying the data type, give the method a name Following the name, add a set of parentheses () Within parenthesis are the parameters taken, if any Code executed by the method is enclosed in brackets {...} After the method is finished, program continues at the line after the call You can use a method anywhere it is legal to use its return type For Example Following code has two methods 1 2 3 4 5 6 7 8 9 10 public class Square5 { public static void main(String[] args) { double result = square(5); System.out.println(result); } static double square(double x) { return x * x; } } Method main calls method square, passing an argument of 5 Method square takes the argument, computes the squares and returns the result What would be returned if we passed square an argument of 4? Method Naming Conventions Use verbs to name methods, since they perform an action Start method names with a lower case letter Further information: The Java Language Specification: 6.8.3 Method Names Static Methods Until we cover objects, all our methods must use the qualifier static If you forget the static keyword, you get a message like: Can't make static reference to method ^ top 3.1.4: Passing Values Passing values to methods increases their usefulness and flexibility Input values for methods are called parameters or passed values When a method is called the supplied values are known as arguments Can specify zero, one or more parameters for a method Definition of method must specify data types and names Note that parameters look like variable declarations Difference is that parameters are initialized by arguments Separate multiple parameters with a comma returnType methodName(Type1 param1, Type2 param2, ...) { ... } Calling method must put values of the same data type, in the same order, inside the parentheses For Example 1 2 3 4 5 6 7 8 9 10 public class Square5 { public static void main(String[] args) { double result = square(5); System.out.println(result); } static double square(double x) { return x * x; } } Passing Primitive Data Types All types in Java are passed-by-value (a.k.a. call-by-value) When a method is called, the value of each argument is copied to its corresponding parameter Values passed as arguments cannot be changed outside the method A method only gets a copy of the variable's value Coercion of Arguments Coercion: forcing arguments to appropriate types Java automatically converts narrower data types to broader data types byte => short => int => long => float => double / char =/ In our example, coercion was used when passing 5 to method square 5 is an integer Method square expects a double Can also coerce the evaluation of methods For example: System.out.println(square(5)); Since square(5) is not something that can be used directly First evaluates: square(5) Then evaluates: System.out.println() ^ top 3.1.5: Returning A Value Return Statement Methods that return a value must execute a return statement Can includes a literal value, variable or expression to return For example: 1 2 3 4 5 6 7 8 9 10 public class Square5 { public static void main(String[] args) { double result = square(5); System.out.println(result); } static double square(double x) { return x * x; } } Method square uses a return statement because it returns a value Method main does not return a value A return statement is optional if no value is returned The return jump occurs automatically at the end of the method Exiting Early In some cases you do not want to execute all the code in a method Use return statement to stop execution and return immediately ^ top 3.1.6: Local Variables and Scope Scope is the region of a program where you can access a variable Variables defined in methods can only be accessed within that method Local variables and method parameters can only be accessed within their block Blocks begin at an opening brace ({) and end at a closing brace (}) Variables declared inside a block are known only inside that block When the block finishes executing, local variables disappear References to local variables outside their block cause a compile-time error For Example Will the following code compile? 1 2 3 4 5 6 7 8 public class Scope { public static void main(String[] args) { for (int count = 0; count < 5; ++count) { System.out.println(count); } System.out.println(count); //cannot resolve symbol } } How do you fix this problem? ^ top 3.1.7: Overloading Methods You can have several methods with the same name in a class However, each method must have a different parameter list (a.k.a. signature) for each method Number of parameters Parameter types Order of parameters Return type is not part of the signature Compiler cannot distinguish between two methods with the same name and signature For Example 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public class SquareTypes { public static void main(String[] args) { System.out.println(square(6.5)); System.out.println(square(5)); } static double square(double x) { System.out.print("Using type double: "); return x * x; } static int square(int x) { System.out.print("Using type int: "); return x * x; } } First call to square uses method with a double signature Second call uses method with an int signature Using type double: 42.25 Using type int: 25 ^ top Exercise 3.1 Take one minute to prepare an answer the following questions. Which of the following code fragments are valid method declarations? methodA() { /*...*/ } void methodB { /*...*/ } void methodC() { /*...*/ } void methodD(void) { /*...*/ } ^ top 3.2: Recursion Objectives At the end of the lesson the student will be able to: Use recursive algorithms to solve problems Implement recursive solutions in Java "To understand recursion, one must first understand recursion." -- Unknown ^ top 3.2.1: About Recursion Recursion: when an algorithm is defined in terms of itself. Recursion is a natural approach to some problems It allows us to break down a problem into one or more subproblems similar in form to the original problem Sounds circular, but in practice is not Recursion divides the problem into two parts: Recursive step Base case The recursive step solves part of the problem Then it calls the method again and passes it the smaller problem Eventually the smaller problem becomes easy enough to just solve The easy-to-solve problem is known as the base case For Example: Many Hands Make Light Work What if you were asked to do some repetitive task like: folding the clothes? You look at the laundry basket and realize you have better things to do So you fold one item and then ask someone else to fold the clothes Then you leave as soon as possible The next person notices your actions and decides to do the same They fold one item and then ask someone else to fold the clothes This sequence repeats until all the clothes are folded Writing this as an algorithm, we have: Algorithm For Folding Clothes If the basket is empty, do nothing Else: Fold one item Ask someone else to fold the clothes Recursive Elements Notice the recursive nature of the algorithm The "else" clause contains a reference to itself To fold the clothes, we ask someone else to fold the clothes To make sure this algorithm is not an endless passing of the buck, each person does some work This makes the job passed to the next person smaller When all the clothes are folded, the chain of asking someone else to fold the clothes is broken ^ top 3.2.2: Implementing Recursive Methods Recursion is an easy and powerful way of tackling many difficult computing problems You implement recursion using methods that call themselves Like a loop, a recursive method must have some way to end Usually the base case is written first and the recursive step second Recursive Method Structure returnType recursiveMethod(parameters) { If (stopping condition) { // base case // Problem is very easy // so solve it and return } else { // recursive step // Solve part of the problem // leaving a smaller problem recursiveMethod(arguments); } } For Example import java.util.Scanner; public class FoldClothes { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.print("How many clothes to fold? "); int count = input.nextInt(); fold(count); } // The recursive method static void fold(int count) { if (count == 0) { System.out.println("Done folding clothes"); return; } else { System.out.print("Folding one item; "); count = count - 1; System.out.println("number reamining: " + count); fold(count); } } } ^ top 3.2.3: Factorial: Classic Recursion To develop a recursive algorithm, we must find a way to do the following: Use a solution to a smaller or easier version of a problem to arrive at the solution itself Know when the problem is small enough to solve directly As another example of recursion, let us look at factorials Recall that a factorial, which is written n!, has the following definition: When n = 0 n! = 1 And for values of n greater than 0: n! = n * (n-1) * (n-2) * (n-3) * ... * 1 We can use this definition to write a Java method that implements factorial One version in psuedocode is: If n is 0, return 1 Else Get the factorial of n - 1 Multiply n time factorial of n - 1 Once we have the psuedocode, conversion to Java code is straightforward static long factorial(int n) { if (n == 0) { return 1; } else { return n * factorial(n - 1); } Note how the method calls itself Instrumenting the Code Often improves understanding to print the method calls and returns However, it does "clutter" the code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 import java.util.Scanner; public class FactorialApp { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.println("I calculate factorials"); System.out.print("Size of factorial: "); int n = input.nextInt(); System.out.println("main() calls factorial(" + n + ")"); long result = factorial(n); System.out.println("main() gets " + result); } static long factorial(int n) { if (n <= 0) { System.out.println("factorial(" + n + ") " + "returns 1"); return 1; } else { System.out.println("factorial(" + n + ") " + "calling " + "factorial(" + (n - 1) + ")"); long fact = n * factorial(n - 1); System.out.println("factorial(" + n + ") " + "returns " + fact); return fact; } } } Tracing the Execution Here is the output of the instrumented code for factorial(3) Added indentations to see the method calls and returns more easily main() calls factorial(3) factorial(3) calling factorial(2) factorial(2) calling factorial(1) factorial(1) calling factorial(0) factorial(0) returns 1 factorial(1) returns 1 factorial(2) returns 2 factorial(3) returns 6 main() gets 6 Note that the first half makes successive method calls Until the base case is reached Second half returns the values of the recursive case ^ top 3.2.4: Recursion and the Call Stack To understand how Java makes recursive method calls, we must consider a data structure known as a stack A stack is like a pile of dishes When a dish is placed on the stack, it is usually placed on top Known as pushing the dish onto the stack Similarly, when a dish is removed from the stack, it is taken from the top Known as popping the dish off the stack The last dish put on the stack is the first dish removed from the stack Otherwise you get a lot of broken dishes Method Call Stack When a program calls a method, it must know how to return to its caller To make this possible, it pushes all the information it needs to remember onto a stack Return address Local variables This stack is known as the method call stack The information saved is known as the activation record or stack frame Every method call creates a new activation record Every time a method returns, its data is popped off the stack Call Stack for factorial(3) ^ top 3.2.5: Recursion Versus Iteration All recursive algorithms or methods can be rewritten without recursion Methods rewritten without recursion usually have loops, so they are called iterative methods Iteration Uses repetition structures (for, while or do-while) Repetition through explicit use of repetition structure Terminates when the loop-condition fails Controls repetition by using a counter or similar mechanism Recursion Uses selection structures (if, if-else or switch) Repetition through repeated method calls Terminates when base case is satisfied Controls repetition by a parameter reaching the base case Recursion vs Iteration Recursion has more overhead than iteration Recursion more memory intensive than iteration Recursion often can be implemented with only a few lines of code Iterative methods generally run faster and use less memory space When should you use recursion? When efficiency is not important and it makes the code easier to understand ^ top 3.2.6: Iteration to Recursion Common practice to convert recursive methods to iterative code Often improves performance Similarly, you can convert any iterative structures to recursive methods Not often useful in practice, but a good way to learn about recursion As an example, we will convert the following program to use recursion import java.util.Scanner; public class SumNums { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.println("I sum from 1 to n"); System.out.print("Enter n: "); int n = input.nextInt(); int counter = 1; int sum = 0; while (counter < n) { //loop body sum = counter + sum; counter++; } System.out.println("Total sum = " + sum); } } General steps are: Determine what variables the loop uses Write a recursive method header with one parameter for each variable Use the condition that causes the termination of the iterative loop as the base case Develop expressions representing how each variable changes from one iteration to the next and make the recursive call using these expressions Replace the original iterative loop with a call to the recursive method, using the initial value of each of the variables as arguments Lets follow these steps with our example 1. Determine the Variables the Loop Uses Within the loop we see three variables used: int counter: loop counter for counter-controlled repetition int n: the upper end of the summation range int sum: accumulator for the summation 2. Write the Method Header The method parameter list must include each of our identified variables Also need to specify a return type for returning the result of our recursion Since we need the sum as an int value, we specify an int return type One possible method header is: static int calcSum(int n, int counter, int sum) 3. Write the Base Case Use the condition that causes the loop termination as the base case Often need to reverse the condition to get the correct test if (counter >= n) { return sum; } 4. Write the Recursive Call Determine how each variable changes from one iteration to the next Develop expressions that represent the changes Use the expressions in the recursive call In our case, we see two changes for each iteration: sum = counter + sum; count++; We can use these statements directly before our recursive call sum = counter + sum; count++; return calcSum(n, sum, counter); We see we can convert these simple statements to expressions Thus we can make the recursive call a "one liner" return calcSum(n, counter + sum, ++counter); Why did we change to prefix increment operator for count? Putting the entire method together, we have: static void counter(int count) { if (count <= 0) { return; } else { return calcSum(n, counter + sum, ++counter); } } 5. Call the Recursive Method Replace the original iterative loop with a call to the recursive method Use the initial value of each of the variables as arguments For our example, need to call the recursive method with one value int sum = calcSum(n, 0, 1; Two of the arguments are constant values Common for recursive practitioners to hide the details using another function call static int calcSum(int n) { return calcSum(n, 0, 1); } All Together Now Converting our original program into a recursive program: import java.util.Scanner; public class SumNumsRec { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.println("I sum from 1 to n"); System.out.print("Enter n: "); int n = input.nextInt(); int sum = calcSum(n); System.out.println("Total sum = " + sum); } static int calcSum(int n) { return calcSum(n, 0, 1); } static int calcSum(int n, int sum, int counter) { if (counter >= n) { return sum; } else { return calcSum(n, counter + sum, ++counter); } } } ^ top 3.2.7: Summary Recursion is when an algorithm is defined in terms of itself Allows us to define subproblems in similar form to the original Recursion always has two parts: Base case A problem that is closer to the solution Eventually, the base case is always called Without the base case, you would have infinite recursion Since recursion is more computationally expensive, it is common to convert recursion to iteration To aid our understanding of recursion, we developed a procedure to convert iteration to recursion More Information For the definition of recursion, see recursion :) Recursion: from Wikipedia ^ top Exercise 3.2 Take two minutes to convert the following iterative code to recursive code: 1 2 3 4 5 6 7 8 public class CountDown { public static void main(String[] args) { int count; for (count = 5; count > 0; count--) { System.out.println(count); } } } Five-Step Procedure Determine what variables the loop uses Write a recursive method header with one parameter for each variable Use the condition that causes the termination of the iterative loop as the base case Develop expressions representing how each variable changes from one iteration a the next and make the recursive call using these expressions Replace the original iterative loop with a call to the recursive method, using the initial value of each of the variables as arguments One possible answer ^ top Wrap Up Due Next: A3: Factorials of Interest (3/2/05) ^ top Home | WebCT | Announcements | Schedule | Room Policies | Course Info Help | FAQ's | HowTo's | Links Last Updated: March 19 2005 @19:47:02