# 1 - Michigan State University

1 1 5 Recursion 1992-2007 Pearson Education, Inc. All rights reserved. 2 We must learn to explore all the options and possibilities that confront us in a complex and rapidly changing world. James William Fulbright O! thou hast damnable iteration, and art indeed able to corrupt a saint. William Shakespeare It's a poor sort of memory that only works backwards. Lewis Carroll, Alice in Wonderland Life can only be understood backwards; but it must be lived forwards. Soren Kierkegaard Push onkeep moving. Thomas Morton 1992-2007 Pearson Education, Inc. All rights reserved. 3 OBJECTIVES In this chapter you will learn:

The concept of recursion. How to write and use recursive methods. How to determine the base case and recursion step in a recursive algorithm. How recursive method calls are handled by the system. The differences between recursion and iteration, and when it is appropriate to use each. What geometric shapes called fractals are and how to draw them using recursion. What recursive backtracking is and why it is an effective problem-solving technique. 1992-2007 Pearson Education, Inc. All rights reserved. 4 15.1 Introduction 15.2 Recursion Concepts 15.3 Example Using Recursion: Factorials 15.4

Example Using Recursion: Fibonacci Series 15.5 Recursion and the Method Call Stack 15.6 Recursion vs. Iteration 15.7 Towers of Hanoi 15.8 Fractals 15.9 Recursive Backtracking 15.10 Wrap-Up 15.11 Internet and Web Resources

1992-2007 Pearson Education, Inc. All rights reserved. 5 15.1 Introduction Earlier programs structured as methods that call one another in a disciplined, hierarchical manner Recursive methods Call themselves Useful for some problems to define a method to call itself Can be called directly or indirectly through another method 1992-2007 Pearson Education, Inc. All rights reserved. 6 Chapter Recursion examples and exercises in this book 15 Factorial Method (Fig. 15.3 and Fig. 15.4) Fibonacci Method (Fig. 15.5 and Fig. 15.6) Towers of Hanoi (Fig. 15.13 and Fig. 15.14) Fractals (Fig. 15.21 and Fig. 15.22) What Does This Code Do? (Exercise 15.7, Exercise 15.12 and Exercise 15.13) Find the Error in the Following Code (Exercise 15.8) Raising an Integer to an Integer Power (Exercise 15.9)

Visualizing Recursion (Exercise 15.10) Greatest Common Divisor (Exercise 15.11) Determine Whether a String Is a Palindrome (Exercise 15.14) Eight Queens (Exercise 15.15) Print an Array (Exercise 15.16) Print an Array Backward (Exercise 15.17) Minimum Value in an Array (Exercise 15.18) Star Fractal (Exercise 15.19) Maze Traversal Using Recursive Backtracking (Exercise 15.20) Generating Mazes Randomly (Exercise 15.21) Mazes of Any Size (Exercise 15.22) Time Needed to Calculate a Fibonacci Number (Exercise 15.23) Fig. 15.1 | Summary of the 32 recursion examples and exercises in this text. (Part 1 of 2) 1992-2007 Pearson Education, Inc. All rights reserved. 7 Chapter Recursion examples and exercises in this book 16 Merge Sort (Fig. 16.10 and Fig. 16.11) Linear Search (Exercise 16.8) Binary Search (Exercise 16.9)

Quicksort (Exercise 16.10) 17 Binary-Tree Insert (Fig. 17.17) Preorder Traversal of a Binary Tree (Fig. 17.17) Inorder Traversal of a Binary Tree (Fig. 17.17) Postorder Traversal of a Binary Tree (Fig. 17.17) Print a Linked List Backward (Exercise 17.20) Search a Linked List (Exercise 17.21) Fig. 15.1 | Summary of the 32 recursion examples and exercises in this text. (Part 2 of 2) 1992-2007 Pearson Education, Inc. All rights reserved. 8 15.2 Recursion Concepts Recursive problem-solving elements Base case Recursive method capable of solving only simplest casethe base case If method is called with base case, method returns result If method is called with more complex problem, problem divided into two piecesa piece the method knows how to do and a piece the method does not know how to do (called recursive call or recursion step) Recursive call/recursion step Must resemble original problem but be slightly simpler or smaller version

Method calls fresh copy of itself to work on smaller problem Normally includes return statement Indirect recursion Recursive method calls another method that eventually makes call back to recursive method 1992-2007 Pearson Education, Inc. All rights reserved. 15.3 Example Using Recursion: Factorials 9 Factorial of n, or n! is the product n (n 1) (n 2) 1 With 1! equal to 1 and 0! Defined to be 1. Can be solved recursively or iteratively (nonrecursively) Recursive solution uses following relationship: n! = n (n 1)! Infinite recursion recursive calls are continuously made until memory has been exhausted Caused by either omitting base case or writing recursion step that does not converge on base case 1992-2007 Pearson Education, Inc. All rights reserved. 10

Fig. 15.2 | Recursive evaluation of 5!. 1992-2007 Pearson Education, Inc. All rights reserved. 1 // Fig. 15.3: FactorialCalculator.java 2 3 4 5 // Recursive factorial method. 11 public class FactorialCalculator { 6 7 8 9 10 // recursive method factorial public long factorial( long number ) {

if ( number <= 1 ) // test for base case return 1; // base cases: 0! = 1 and 1! = 1 11 12 13 14 15 else // recursion step return number * factorial( number - 1 ); } // end method factorial // output factorials for valuesPortion 0-10 16 17 public void displayFactorials() { Base case returns 1 Recursion step breaks problem into two parts: one the method knows how to do, one the method does not methodRecursive knows how call: to Portion

do method does not know how to do; smaller version of original problem 18 // calculate the factorials of 0 through 10 19 for ( int counter = 0; counter <= 10; counter++ ) 20 System.out.printf( "%d! = %d\n", counter, factorial( counter ) ); 21 } // end method displayFactorials 22 } // end class FactorialCalculator Original call to recursive method 1992-2007 Pearson Education, Inc. All rights reserved. 12 Common Programming Error 15.1 Either omitting the base case or writing the recursion step incorrectly so that it does not converge on the base case can cause a logic error known as infinite recursion, where recursive calls are continuously made until memory has been exhausted. This error is analogous to the problem of an infinite loop in an iterative (nonrecursive) solution.

1992-2007 Pearson Education, Inc. All rights reserved. 1 // Fig. 15.4: FactorialTest.java 2 // Testing the recursive factorial method. 13 3 4 public class FactorialTest 5 { 6 // calculate factorials of 0-10 7 public static void main( String args[] ) 8

{ 9 Calculate and display FactorialCalculator factorialCalculator = new FactorialCalculator(); 10 factorialCalculator.displayFactorials(); 11 factorials } // end main 12 } // end class FactorialTest 0! = 1 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880 10! = 3628800

1992-2007 Pearson Education, Inc. All rights reserved. 15.4 Example Using Recursion: Fibonacci Series 14 Fibonacci series begins with 0 and 1 and has property that each subsequent Fibonacci number is the sum of previous two Fibonacci numbers. Series occurs in nature, ratio of successive Fibonacci numbers converges on golden ratio or golden mean Fibonacci series defined recursively as: fibonacci(0) = 0 fibonacci(1) = 1 fibonacci(n) = fibonacci(n 1) + fibonacci(n 2) Recursive solution for calculating Fibonacci values results in explosion of recursive method calls 1992-2007 Pearson Education, Inc. All rights reserved. 1 // Fig. 15.5: FibonacciCalculator.java 2 // Recursive fibonacci method.

3 4 5 6 public class FibonacciCalculator { // recursive declaration of method fibonacci 15 Two base cases 7 8 9 10 11 public long fibonacci( long number ) { if ( ( number == 0 ) || ( number == 1 ) ) // base cases return number; else // recursion step 12 13 14 15

16 return fibonacci( number - 1 ) + fibonacci( number - 2 ); } // end method fibonacci Two recursive calls public void displayFibonacci() { 17 for ( int counter = 0; counter <= 10; counter++ ) 18 System.out.printf( "Fibonacci of %d is: %d\n", counter, 19 fibonacci( counter ) ); 20 } // end method displayFibonacci 21 } // end class FibonacciCalculator Original call to recursive method 1992-2007 Pearson Education, Inc. All rights reserved. 1 // Fig. 15.6: FibonacciTest.java 2

// Testing the recursive fibonacci method. 16 3 4 public class FibonacciTest 5 { 6 public static void main( String args[] ) 7 { 8 Calculate and display FibonacciCalculator fibonacciCalculator = new FibonacciCalculator(); 9 fibonacciCalculator.displayFibonacci();

10 Fibonacci values } // end main 11 } // end class FibonacciTest Fibonacci Fibonacci Fibonacci Fibonacci Fibonacci Fibonacci Fibonacci Fibonacci Fibonacci Fibonacci Fibonacci of of of of of of of of of of of

0 is: 0 1 is: 1 2 is: 1 3 is: 2 4 is: 3 5 is: 5 6 is: 8 7 is: 13 8 is: 21 9 is: 34 10 is: 55 1992-2007 Pearson Education, Inc. All rights reserved. 17 Fig. 15.7 | Set of recursive calls for fibonacci( 3 ). 1992-2007 Pearson Education, Inc. All rights reserved. 18 Performance Tip 15.1 Avoid Fibonacci-style recursive programs, because they result in an exponential explosion of method calls. 1992-2007 Pearson Education, Inc. All rights reserved.

15.5 Recursion and the Method Call Stack 19 Method call stack used to keep track of method calls and local variables within a method call Just as with nonrecursive programming, recursive method calls are placed at the top of the method call stack As recursive method calls return, their activation records are popped off the stack and the previous recursive calls continue executing Current method executing is always method whose activation record is at top of stack 1992-2007 Pearson Education, Inc. All rights reserved. 20 Fig. 15.8 | Method calls made within the call fibonacci( 3 ). 1992-2007 Pearson Education, Inc. All rights reserved. 21 Fig. 15.9 | Method calls on the program execution stack. 1992-2007 Pearson Education, Inc. All rights reserved.

22 15.6 Recursion vs. Iteration Any problem that can be solved recursively can be solved iteratively Both iteration and recursion use a control statement Iteration uses a repetition statement Recursion uses a selection statement Iteration and recursion both involve a termination test Iteration terminates when the loop-continuation condition fails Recursion terminates when a base case is reached Recursion can be expensive in terms of processor time and memory space, but usually provides a more intuitive solution 1992-2007 Pearson Education, Inc. All rights reserved. 1 2 3 4 5 6 7 8 9 10

// Fig. 15.10: FactorialCalculator.java // Iterative factorial method. 23 public class FactorialCalculator { // recursive declaration of method factorial public long factorial( long number ) { long result = 1; // iterative declaration of method factorial for ( long i = number; i >= 1; i-- ) result *= i; Iterative solution uses counter-controlled repetition 11 12 13 14 15 16 return result; } // end method factorial 17 18 19

20 21 22 // output factorials for values 0-10 public void displayFactorials() { // calculate the factorials of 0 through 10 for ( int counter = 0; counter <= 10; counter++ ) 23 System.out.printf( "%d! = %d\n", counter, factorial( counter ) ); 24 } // end method displayFactorials 25 } // end class FactorialCalculator 1992-2007 Pearson Education, Inc. All rights reserved. 1 // Fig. 15.11: FactorialTest.java 2 // Testing the iterative factorial method. 24 3 4

public class FactorialTest 5 { 6 // calculate factorials of 0-10 7 public static void main( String args[] ) 8 { 9 FactorialCalculator factorialCalculator = new FactorialCalculator(); 10 factorialCalculator.displayFactorials(); 11 } // end main

12 } // end class FactorialTest 0! = 1 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880 10! = 3628800 1992-2007 Pearson Education, Inc. All rights reserved. 25 Software Engineering Observation 15.1 Any problem that can be solved recursively can also be solved iteratively (nonrecursively). A recursive approach is normally preferred over an iterative approach when the recursive approach more naturally mirrors the problem and results in a program that is easier to understand and debug. A recursive approach can often be implemented with fewer lines of code. Another reason to choose a recursive approach is that an iterative one might not be apparent.

1992-2007 Pearson Education, Inc. All rights reserved. 26 Performance Tip 15.2 Avoid using recursion in situations requiring high performance. Recursive calls take time and consume additional memory. 1992-2007 Pearson Education, Inc. All rights reserved. 27 Common Programming Error 15.2 Accidentally having a nonrecursive method call itself either directly or indirectly through another method can cause infinite recursion. 1992-2007 Pearson Education, Inc. All rights reserved. 28 15.7 Towers of Hanoi Classic problem Priests in Far East are attempting to move a stack of disks from one peg to another. One disk must be moved at a time, at no time may a larger disk be placed above a smaller disk Recursive solution: Move n 1 disks from peg 1 to peg 2, using peg 3 as temporary holding area

Move the last disk (the largest) from peg 1 to peg 3 Move the n 1 disks from peg 2 to peg 3, using peg 1 as a temporary holding area Base case: When only one disk needs to be moved no temporary holding area needed, disk is simply moved 1992-2007 Pearson Education, Inc. All rights reserved. 29 Fig. 15.12 | Towers of Hanoi for the case with four disks. 1992-2007 Pearson Education, Inc. All rights reserved. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

16 17 18 19 20 21 22 23 24 // Fig. 15.13: TowersOfHanoi.java // Program solves the towers of Hanoi problem, and // demonstrates recursion. 30 public class TowersOfHanoi { int numDisks; // number of disks to move public TowersOfHanoi( int disks ) { numDisks = disks; } // end TowersOfHanoi constructor // recusively move disks through towers public void solveTowers( int disks, int sourcePeg, int destinationPeg, int tempPeg ) { // base case -- only one disk to move if ( disks == 1 ) Base case: Simply

{ System.out.printf( "\n%d --> %d", sourcePeg, destinationPeg ); return; } // end if display move 1992-2007 Pearson Education, Inc. All rights reserved. 25 // recursion step -- move disk to tempPeg, then to destinationPeg 26 // move ( disks - 1 ) disks from sourcePeg to tempPeg recursively 27 solveTowers( disks - 1, sourcePeg, tempPeg, destinationPeg ); 28 29 30 Move last disk from peg 1 to peg 3 // move last disk from sourcePeg to destinationPeg Move

n-1 disks from peg peg 1 to 3peg as System.out.printf( "\n%d --> %d", sourcePeg, destinationPeg ); Use temporary 2 holding area 31 32 // move ( disks - 1 ) disks from tempPeg to destinationPeg 33 solveTowers( disks - 1, tempPeg, destinationPeg, sourcePeg ); 34 31 } // end method solveTowers 35 } // end class TowersOfHanoi as temporary

Move n-1 disks from Use peg peg 2 to 1peg 3 holding area 1992-2007 Pearson Education, Inc. All rights reserved. 1 2 3 // Fig. 15.14: TowersOfHanoiTest.java // Test the solution to the Towers of Hanoi problem. 4 5 public class TowersOfHanoiTest { 32 6 public static void main( String args[] ) 7 { 8 int startPeg = 1; // value 1 used to indicate startPeg in output

9 int endPeg = 3; // value 3 used to indicate endPeg in output 10 int tempPeg = 2; // value 2 used to indicate tempPeg in output 11 int totalDisks = 3; // number of disks 12 TowersOfHanoi towersOfHanoi = new TowersOfHanoi( totalDisks ); 13 Make initial 14 // initial nonrecursive call: move all disks. 15 towersOfHanoi.solveTowers( totalDisks, startPeg, endPeg, tempPeg ); 16 } // end main 17 } // end class TowersOfHanoiTest 1 1 3 1 2 2 1 --> --> -->

--> --> --> --> call to recursive method 3 2 2 3 1 3 3 1992-2007 Pearson Education, Inc. All rights reserved. 33 15.8 Fractals Fractal a geometric figure that often can be generated from a pattern repeated recursively an infinite number of times Pattern applied to each segment of original figure Benoit Mandelbrot introduced term fractal, along with specifics of how fractals are created and their practical applications Help us better understand patterns in nature, the human body and the universe Popular art form

1992-2007 Pearson Education, Inc. All rights reserved. 34 15.8 Fractals Self-similar property fractals have this property in the case that, when subdivided into parts, each resembles a reduced-size copy of the whole If part is exact copy of original, fractal is said to be strictly self similar Each time pattern is applied, fractal is said to be at new level or depth Fractal examples: Koch Curve, Koch Snowflake 1992-2007 Pearson Education, Inc. All rights reserved. (a) (b) (c) (d) (e) (f) 35

1992-2007 Pearson Education, Inc. All rights reserved. 40 Fig. 15.20 | Lo fractal at level 2. 1992-2007 Pearson Education, Inc. All rights reserved. 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 // Fig. 15.21: Fractal.java // Demonstrates user interface for drawing a fractal. import java.awt.Color; import java.awt.FlowLayout; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import javax.swing.JFrame; import javax.swing.JButton; import javax.swing.JLabel; import javax.swing.JPanel; import javax.swing.JColorChooser; 41 public class Fractal extends JFrame { private final int WIDTH = 400; // define width of GUI private final int HEIGHT = 480; // define height of GUI private final int MIN_LEVEL = 0; private Color color = Color.BLUE; private JButton changeColorJButton, increaseLevelJButton,

decreaseLevelJButton; private JLabel levelJLabel; private FractalJPanel drawSpace; private JPanel mainJPanel, controlJPanel; // set up GUI public Fractal() { super( "Fractal" ); 1992-2007 Pearson Education, Inc. All rights reserved. 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

50 51 52 53 54 55 // set up control panel controlJPanel = new JPanel(); controlJPanel.setLayout( new FlowLayout() ); 42 // set up color button and register listener changeColorJButton = new JButton( "Color" ); controlJPanel.add( changeColorJButton ); changeColorJButton.addActionListener( new ActionListener() // anonymous inner class { // process changeColorJButton event public void actionPerformed( ActionEvent event ) { color = JColorChooser.showDialog( Fractal.this, "Choose a color", color ); // set default color, if no color is returned if ( color == null ) color = Color.BLUE; drawSpace.setColor( color ); } // end method actionPerformed } // end anonymous inner class

); // end addActionListener 1992-2007 Pearson Education, Inc. All rights reserved. 56 57 // set up decrease level button to add to control panel and // register listener 58 59 60 61 62 63 64 decreaseLevelJButton = new JButton( "Decrease Level" ); controlJPanel.add( decreaseLevelJButton ); decreaseLevelJButton.addActionListener( new ActionListener() // anonymous inner class { // process decreaseLevelJButton event public void actionPerformed( ActionEvent event ) 65 66 67 68

{ int level = drawSpace.getLevel(); level--; // decrease level by one 69 70 // modify level if possible if ( level >= MIN_LEVEL ) 71 72 73 { 74 75 repaint(); } // end if 76 77 78 79 levelJLabel.setText( "Level: " + level ); drawSpace.setLevel( level );

} // end method actionPerformed } // end anonymous inner class ); // end addActionListener 43 Retrieve current level Decrease level Set new level Redraw fractal up to new level 1992-2007 Pearson Education, Inc. All rights reserved. 80 81 // set up increase level button to add to control panel // and register listener 82 83 84 85 86 87 88

increaseLevelJButton = new JButton( "Increase Level" ); controlJPanel.add( increaseLevelJButton ); increaseLevelJButton.addActionListener( new ActionListener() // anonymous inner class { // process increaseLevelJButton event public void actionPerformed( ActionEvent event ) 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 { int level = drawSpace.getLevel(); level++; // increase level by one

// modify level if possible if ( level >= MIN_LEVEL ) { levelJLabel.setText( "Level: " + level ); drawSpace.setLevel( level ); repaint(); } // end if } // end method actionPerformed Redraw fractal up } // end anonymous inner class 44 Retrieve current level Increase level Set new level to new level ); // end addActionListener // set up levelJLabel to add to controlJPanel levelJLabel = new JLabel( "Level: 0" ); controlJPanel.add( levelJLabel ); 107 1992-2007 Pearson Education, Inc. All rights reserved. 108

drawSpace = new FractalJPanel( 0 ); 109 110 111 // create mainJPanel to contain controlJPanel and drawSpace mainJPanel = new JPanel(); 45 112 mainJPanel.add( controlJPanel ); 113 mainJPanel.add( drawSpace ); 114 115 add( mainJPanel ); // add JPanel to JFrame 116 117 setSize( WIDTH, HEIGHT ); // set size of JFrame 118 setVisible( true ); // display JFrame 119 } // end Fractal constructor 120 121 public static void main( String args[] ) 122

{ 123 Fractal demo = new Fractal(); 124 demo.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE ); 125 } // end main 126 } // end class Fractal 1992-2007 Pearson Education, Inc. All rights reserved. 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 // Fig. 15.22: FractalJPanel.java // FractalJPanel demonstrates recursive drawing of a fractal. import java.awt.Graphics; import java.awt.Color; import java.awt.Dimension; import javax.swing.JPanel; 46 public class FractalJPanel extends JPanel { private Color color; // stores color used to draw fractal private int level; // stores current level of fractal private final int WIDTH = 400; // defines width of JPanel private final int HEIGHT = 400; // defines height of JPanel // set the initial fractal level to the value specified // and set up JPanel specifications public FractalJPanel( int currentLevel ) { color = Color.BLUE; // initialize drawing color to blue level = currentLevel; // set initial fractal level setBackground( Color.WHITE );

setPreferredSize( new Dimension( WIDTH, HEIGHT ) ); } // end FractalJPanel constructor 1992-2007 Pearson Education, Inc. All rights reserved. 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

51 // draw fractal recursively public void drawFractal( int level, int xA, int yA, int xB, 47 int yB, Graphics g ) { Coordinates of first point for line // base case: draw a line connecting two given points Coordinates ofissecond for line where fractal being point applied if ( level == 0 ) where fractal is being applied g.drawLine( xA, yA, xB, yB ); Base case: Simply draw line, pattern is else // recursion step: determine new points, draw next level not applied { // calculate midpoint between (xA, yA) and (xB, yB) int xC = ( xA + xB ) / step: 2; Apply fractal pattern

Recursion Calculate midpoint int yC = ( yA + yB ) / 2; // calculate the fourth point (xD, yD) which forms an // isosceles right triangle between (xA, yA) and (xC, yC) // where the right angle is at (xD, yD) int xD = xA + ( xC - xA ) / 2 - ( yC - yA ) / 2; int yD = yA + ( yC - yA ) / 2 + ( xC - xA ) / 2; Calculate point to form right triangle // recursively draw the Fractal drawFractal( level - 1, xD, yD, xA, yA, g ); drawFractal( level - 1, xD, yD, xC, yC, g ); drawFractal( level - 1, xD, yD, xB, yB, g ); } // end else } // end method drawFractal Apply pattern to three new lines 1992-2007 Pearson Education, Inc. All rights reserved. 52 53 54 55 56 57 58

59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 // start drawing the fractal public void paintComponent( Graphics g ) { super.paintComponent( g ); // draw fractal pattern g.setColor( color ); drawFractal( level, 100, 90, 290, 200, g ); } // end method paintComponent 48 Make first call to recursive method whenever window is repainted

// set the drawing color to c public void setColor( Color c ) { color = c; } // end method setColor // set the new level of recursion public void setLevel( int currentLevel ) { level = currentLevel; } // end method setLevel 1992-2007 Pearson Education, Inc. All rights reserved. 74 // returns level of recursion 75 public int getLevel() 76 { 77 return level; 78 } // end method getLevel 79 } // end class FractalJPanel 49 1992-2007 Pearson Education, Inc. All rights reserved.