UTEP CS 2401 - Recursive Methods and Problem Solving

Unformatted text preview:

Recursive Methods and Problem Solving Chris Kiekintveld CS 2401 (Fall 2010) Elementary Data Structures and AlgorithmsReview: Calling Methods Java Programming: Program Design Including Data Structures 2 int x(int n) { int m = 0; n = n + m + 1; return n; } int y(int n) { int m = 1; n = x(n); return m + n; } What does y(3) return?Calling Methods  Methods can call other methods  Can a method call itself?  Yes! This is called a recursive method (function)  “A method within a method” Java Programming: Program Design Including Data Structures 3Java Programming: Program Design Including Data Structures 4Example Java Programming: Program Design Including Data Structures 5 void test(int n) { if (n > 0) { System.out.println(n); test(n-1); System.out.println(n); } } Trace the execution of test(4)Example (pt 2) Java Programming: Program Design Including Data Structures 6 void test(int n) { if (n > 0) { System.out.println(n); test(n-1); System.out.println(n); } } Trace the execution of test(-4)Java Programming: Program Design Including Data Structures 7 Terminology  A recursive method is any method that calls itself  Base case  VERY IMPORTANT  Stops the recursion (prevents infinite loops)  Solved directly to return a value without calling the same method againJava Programming: Program Design Including Data Structures 8 Recursive Definitions  Directly recursive: method that calls itself  Indirectly recursive: method that calls another method and eventually results in the original method call  Tail recursive method: recursive method in which the last statement executed is the recursive call  Infinite recursion: case where every recursive call results in another recursive callTracing a Recursive Method  As always, go line by line  Recursive methods may have many copies  Every method call creates a new copy and transfers flow of control to the new copy  Each copy has its own:  code  parameters  local variables Java Programming: Program Design Including Data Structures 9Java Programming: Program Design Including Data Structures 10 Tracing a Recursive Method  After completing a recursive call:  Control goes back to the calling environment  Recursive call must execute completely before control goes back to previous call  Execution in previous call begins from point immediately following recursive callFactorial Numbers  Factorial numbers (i.e., n!) defined recursively:  factorial(0) = 1  factorial(n+1) = factorial(n) * n+1  Examples  0! = 1  1! = 1 * 1 = 1  2! = 2 * 1 * 1 = 2  3! = 3 * 2 * 1 * 1 = 6  4! = 4 * 3 * 2 * 1 * 1 = 24 Java Programming: Program Design Including Data Structures 11Java Programming: Program Design Including Data Structures 12 Iterative Factorial Method public static int fact(int num) { int tmp = 1; for (int i = 1; i <= num; i++) { tmp *= i; } return tmp; } Trace fact(5)Java Programming: Program Design Including Data Structures 13 Recursive Factorial Method public static int fact(int num) { if (num == 0) return 1; else return num * fact(num – 1); } Trace fact(5)Java Programming: Program Design Including Data Structures 14 Recursive Factorial TraceJava Programming: Program Design Including Data Structures 15 Recursion or Iteration?  Moral: There is usually more than one way to solve a problem!  Iteration (loops to repeat code)  Recursion (nested function calls to repeat code)  Tradeoffs between two options:  Sometimes recursive solution is easier  Recursive solution is often slowerToday’s Topic: Recursion (Continued) Java Programming: Program Design Including Data Structures 16Facts about Recursion  Recursive methods call themselves  Each call solves an identical problem  The code is the same!  Successive calls solve smaller/simpler instances  Every recursive algorithm has at least one base case  A known/easy to solve case  Often, when we reach 1 or 0 Java Programming: Program Design Including Data Structures 17Designing Recursive Algorithms  General strategy: “Divide and Conquer”  Questions to ask yourself  How can we reduce the problem to smaller version of the same problem?  How does each call make the problem smaller?  What is the base case?  Will you always reach the base case? Java Programming: Program Design Including Data Structures 18Similarities  Closely related to recursive definitions in math  Also closely related to proof by induction  Inductive proofs work in “reverse”  Start by proving a base case  Then show that if it is true for case n, it must also be true for case n+1 Java Programming: Program Design Including Data Structures 19Exercise Write a recursive function that prints the numbers 1…n in descending order: Java Programming: Program Design Including Data Structures 20 public void descending(int n) { }Exercise Write a recursive function that prints the numbers 1…n in descending order: Java Programming: Program Design Including Data Structures 21 public void descending(int n) { if (n <= 0) return; System.out.println(n); descending(n-1); }Exercise Write a recursive function to perform exponentiation return xm, assuming m >= 0 Java Programming: Program Design Including Data Structures 22 public int exp(int x, int m) { }Exercise Write a recursive function to perform exponentiation return xm, assuming m >= 0 Java Programming: Program Design Including Data Structures 23 public int exp(int x, int m) { if (m == 0) { return 1; } if (m == 1) { return x; } return x * exp(x, m-1); }Java Programming: Program Design Including Data Structures 24 public static boolean p(string s, int i, int f) if (i < f) { if (s[i] == s[f]) { return p(s, i+1, f-1); } else { return false; } } else { return true; } } What does p(s,0,s.length-1) return a) if s ="UTEP' b) if s ="SAMS' c) if s ="kayak" d) if s= "ABBA"Towers of Hanoi  The legend of the temple of Brahma  64 golden disks on 3 pegs  The universe will end when the priest move all disks from the first peg to the last Java Programming: Program Design Including Data Structures 25The Rules  Only move one disk at a


View Full Document

UTEP CS 2401 - Recursive Methods and Problem Solving

Documents in this Course
Load more
Download Recursive Methods and Problem Solving
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Recursive Methods and Problem Solving and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Recursive Methods and Problem Solving 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?