CSC 1052 Algorithms & Data Structures II
A recursive definition specifies something in terms of itself, exemplified by a series of numbers. In programming, recursion is a technique where a problem is solved via methods calling themselves, applying solutions to smaller versions of the problem. Each recursive call progresses towards a base case, which is non-recursive and solved directly. For instance, calculating the factorial of a number demonstrates recursion's elegance. However, care must be taken to avoid infinite recursion and stack overflow errors.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSC 1052 Algorithms & Data Structures II Recursion
Recursion A recursive definition defines something in terms of itself For example, a series of numbers could be defined as follows: t1= 0 tn= tn-1+ 4 Therefore: t1= 0 t2= t1+ 4 = 4 t3= t2+ 4 = 8 t4= t3+ 4 = 12 etc. 3
Recursion A recursive definition has: a base case, which is non-recursive, and a recursive part, which references the same concept in some way In programming, recursion is a technique in which a problem is solved by a method calling itself Each call applies the solution to a slightly smaller version of the problem Eventually, the base case is reached, which is solved directly 4
Recursion N factorial, written n!, is the product of all integers from 1 to n 4! = 4 * 3 * 2 * 1 = 24 5! = 5 * 4 * 3 * 2 * 1 = 120 Note that 5! is equal to 4! * 5 Generalizing: n! = n * (n-1)! Base case: 1! = 1 5
Recursion Here's a recursive method to compute n! public static long factorial(int n) { if (n == 1) return 1; // base case else return n * factorial(n-1); // recursive } Note that 20! is the largest problem this will solve without an overflow error This limitation has nothing to do with recursion 6
Recursion Like any method call, recursion is managed using the call stack 7
Recursion A recursive call must eventually result in the base case If not, we say the result is infinite recursion, which eventually causes a StackOverflowError An iterative solution uses loops instead of recursion You typically wouldn't compute n! using recursion since the iterative solution is cleaner The decision to use recursion is an important design choice There is no such thing as a problem that can only be solved using recursion However, the recursive version may be more elegant 8
Recursion Problem: Greatest Common Divisor the largest integer that divides two integers evenly The GCD of 16 and 24 is 8 The GCD of 100 and 500 is 100 Here's a recursive version of Euclid's Algorithm: gcd(m, n) equals n if n divides m equally Otherwise, gcd(m, n) equals gcd(n, m % n) This is particularly efficient compared to other solutions 9
Recursion Recursive implementation of the GCD solution: public static int gcd(int m, int n) { if (m % n == 0) // base case return n; else return gcd(n, m % n); // recursive } 10
Recursion Problem: reversing a string Input: "Recursion rocks" Output: "skcor noisruceR" Base case: a string of length 0 or 1 public static String reverseString(String str) { if (str.length() <= 1) // base case return str; else return reverseString(str.substring(1)) + str.charAt(0); } 11
Recursion Once again, the iterative solution is more straightforward Furthermore, a new String object is created for each recursive call An alternative recursive solution uses overloaded versions of the reverseString method The first takes just the string as the parameter The second takes the string and the index of the "start" character The first version is not recursive, and simply makes the initial call to the second The second is a recursive helper method 12
Recursion public static String reverseString(String str) { return reverseString(str, 0); } private static String reverseString(String str, int start) { if (start == str.length() 1) // base case return str.charAt(str.length() 1) + ""; else return reverseString(str, start + 1) + str.charAt(start); } 13
Example: Palindromes A palindrome is a string that reads the same forwards and backwards radar kayak deified drab bard able was I ere I saw elba Goal: determine if a string is a palindrome For now, spaces, punctuation, and differences in case all affect the conclusion 15
Example: Palindromes The approach: compare the outermost characters and work inwards Must work for an odd or even number of characters Getting an initial string to process: Scanner in = new Scanner(System.in); System.out.print("Enter a string ('q' to quit): "); String str = in.nextLine(); 16
Example: Palindromes while (!str.equals("q")) { int left = 0; int right = str.length() - 1; boolean palindrome = true; while (left < right && palindrome) { if (str.charAt(left) != str.charAt(right)) palindrome = false; else { left++; right--; } } 17
Example: Palindromes The rest of the outer loop: if (palindrome) System.out.println("\"" + str + "\" is a palindrome."); else System.out.println("\"" + str + "\" is not a palindrome."); System.out.println(); System.out.print("Enter a string ('q' to quit): "); str = in.nextLine(); } 18
Example: Palindromes A sample run: Enter a string ('q' to quit): radar "radar" is a palindrome. Enter a string ('q' to quit): banana "banana" is not a palindrome. Enter a string ('q' to quit): able was I ere I saw elba "able was I ere I saw elba" is a palindrome. Enter a string ('q' to quit): to be or not to be "to be or not to be" is not a palindrome. Enter a string ('q' to quit): q 19
Example: Palindromes The following strings would NOT be recognized as palindromes by the previous solution A man, a plan, a canal, Panama. Taco cat Rise to vote, sir. Dennis and Edna sinned. Go hang a salami; I'm a lasagna hog. I prefer pi. Name now one man. Must ignore spaces, punctuation, and differences in case 20
Example: Palindromes Solution: transform the string before it's evaluated str = str.replaceAll("\\W", ""); str = str.toLowerCase(); The first line uses a regular expression to replace all non- word characters with the empty string Enter a string ('q' to quit): Taco cat "tacocat" is a palindrome. Enter a string ('q' to quit): Rise to vote, sir. "risetovotesir" is a palindrome. 21
Example: Recursive Palindromes A palindrome is a string that reads the same forwards and backwards radar kayak deified drab bard able was I ere I saw elba Goal: determine if a string is a palindrome Let's examine a recursive solution 23
Example: Recursive Palindromes A string is a palindrome if its two outermost characters match and the characters between them is a palindrome 24
Example: Recursive Palindromes Our solution will keep passing the original string along with two indexes that represent the "outer" characters to match The isPalindrome method is overloaded The first version is not recursive and calls the second: public static boolean isPalindrome(String str) { return isPalindrome(str, 0, str.length() - 1); } 25
Example: Recursive Palindromes The recursive version of isPalindrome checks for two base cases: a string of length 0 or 1 (when first and last meet or cross) the outer characters do not match private static boolean isPalindrome(String str, int first, int last) { if (last <= first) return true; else if (str.charAt(first) != str.charAt(last)) return false; else return isPalindrome(str, first + 1, last - 1); } 26
Example: Towers of Hanoi The Towers of Hanoi is a puzzle made up of three pegs and a set of disks Goal: move all disks from peg 1 to peg 3, following three rules: Only move one disk at a time A larger disk cannot be put on a smaller disk A disk cannot be moved off the puzzle 27
Example: Towers of Hanoi Our solution produces a series of instructions on how the disks should be moved to solve the puzzle public class TowersSolver { public static void main(String[] args) { TowersOfHanoi puzzle = new TowersOfHanoi(4); puzzle.solve(); } } 29
Example: Towers of Hanoi Move a disk from 1 to 2 Move a disk from 1 to 3 Move a disk from 2 to 3 Move a disk from 1 to 2 Move a disk from 3 to 1 Move a disk from 3 to 2 Move a disk from 1 to 2 Move a disk from 1 to 3 Move a disk from 2 to 3 Move a disk from 2 to 1 Move a disk from 3 to 1 Move a disk from 2 to 3 Move a disk from 1 to 2 Move a disk from 1 to 3 Move a disk from 2 to 3 30
Example: Towers of Hanoi A recursive solution solves a slightly smaller version of itself Moving a stack of N disks can be thought of in terms of moving a stack of N-1 disks Moving a stack of N disks from Peg 1 to Peg 3: Move N-1 disks from Peg 1 to Peg 2 Move the largest disk from Peg 1 to Peg 3 Move N-1 disks from Peg 2 to Peg 3 That is, move a smaller stack out of the way to move the largest disk 31
Example: Towers of Hanoi The recursive workhorse of this solution is called moveTowers, which accepts four parameters: number of disks to move starting peg destination peg peg to use for intermediary storage The pegs will switch roles on each call to the method 32
Example: Towers of Hanoi public class TowersOfHanoi { private int disks; public TowersOfHanoi(int disks) { this.disks = disks; } public void solve() { moveTower(disks, 1, 3, 2); } ... 33
Example: Towers of Hanoi ... public void moveTower(int disksToMove, int start, int end, int temp) { if (disksToMove == 1) System.out.println("Move a disk from " + start + " to " + end); else { moveTower(disksToMove - 1, start, temp, end); System.out.println("Move a disk from " + start + " to " + end); moveTower(disksToMove - 1, temp, end, start); } } } 34
Example: Towers of Hanoi Given the complexity of the problem, the solution is quite short and elegant An iterative solution would be much more complicated The solution is also terribly inefficient Moving a stack of N disks requires 2N-1 individual disk moves This is exponential complexity As the number of disks increases, the number of individual disk moves increases exponentially 35
Example: Towers of Hanoi Number of Disks Number of Moves 4 15 8 255 12 4,095 20 1,048,575 30 1,073,741,823 40 1,099,511,627,775 50 1,125,899,906,842,623 36
Wrapper Classes The Java API contains a set of wrapper classes that correspond to the primitive types Wrapper classes contain constants and methods that help manage the corresponding primitive type They also can be used to represent a primitive value as an object All wrapper classes are part of the java.lang package 38
Wrapper Classes Primitive Type Wrapper Class byte Byte short Short int Integer long Long float Float double Double char Character boolean Boolean Note that Integer and Character are fully spelled out 39
Wrapper Classes System.out.println("Smallest int: " + Integer.MIN_VALUE); System.out.println("Largest int: " + Integer.MAX_VALUE); System.out.println("Number of bits in an int: " + Integer.SIZE); System.out.println(); System.out.println("25 in binary: " + Integer.toBinaryString(25)); System.out.println("25 in octal: " + Integer.toOctalString(25)); System.out.println("25 in hex: " + Integer.toHexString(25)); System.out.println(); String str = "427"; System.out.println("The value in str is " + Integer.parseInt(str)); 40
Wrapper Class Smallest int: -2147483648 Largest int: 2147483647 Number of bits in an int: 32 25 in binary: 11001 25 in octal: 31 25 in hex: 19 The value in str is 427 Double and Float contain constants for POSITIVE_INFINITY, NEGATIVE_INFINITY, and NaN (not a number) The Character class contains various methods such as isDigit, isLetter, isLowerCase, isUpperCase, and isWhiteSpace 41
Wrapper Classes A wrapper class can also be used to create an object that represents a primitive value as an object Integer intObj = new Integer(500); This is useful when a primitive value will not suffice For example, an ArrayList can only hold objects You can't create an ArrayList that holds double values, but you can create an ArrayList that holds Double objects 42
Wrapper Classes As of Java 5, wrapper classes and their corresponding primitive values can be exchanged automatically Converting a primitive value to a wrapper object is called autoboxing Going the other way is called unboxing This conversion happens whenever needed: in expressions, passing parameters, etc. Integer length = 30; length = length * 2; 43
Wrapper Classes Autoboxing and unboxing is not efficient If dealing with many values, consider using a regular array instead of an ArrayList Also note that the wrapper classes are immutable You can't change the value in an Integer object, for instance; you can only create a new one 44
The this Reference Consider the following class that represents a circle public class Circle { private double radius; public Circle() { radius = 1.0; } public Circle(double size) { radius = size; } ... 45
The this Reference public void setRadius(double newSize) { radius = newSize; } public double getArea() { return Math.PI * radius * radius; } public String toString() { return "Radius: " + radius + "\nArea: " + getArea(); } } 46
The this Reference Now suppose another class invokes the following: Circle circle1 = new Circle(4.5); Circle circle2 = new Circle(12.9); double area = circle1.getArea(); The getArea method is called through the circle1 reference variable Thus, the area of a circle with radius 4.5 is computed and returned The radius value used depends on the invocation 47
The this Reference The Java keyword this can be used inside a class to explicitly refer to the object on which a method is invoked public String toString() { return "Radius: " + this.radius + "\nArea: " + this.getArea(); } Since there is no particular need to use the this reference in this case, it is usually omitted 48
The this Reference However, the this reference can be useful For example, it can be used to distinguish a parameter from a piece of instance data public void setRadius(double radius) { this.radius = radius; } This allows you to avoid making up arbitrarily different names for data that represents the same thing 49
The this Reference Constructors often make use of the this reference public Circle() { this(1.0); // calls the other constructor } public Circle(double radius) { this.radius = radius; } It can be used to invoke other constructors as well as distinguish between parameters and instance data 50
