Recursion.ppt 6g3520

Recursion

Lecture Objectives • Learn about recursive definitions • Explore the base case and the general case of a recursive definition

• Learn about recursive algorithms

Lecture Objectives (Cont’d) • Learn about recursive methods • Become aware of direct and indirect recursion

• Explore how to use recursive methods to implement recursive algorithms

Recursive Definitions • Recursion  Process of solving a problem by reducing it to smaller versions of itself

• Recursive definition  Definition in which a problem is expressed in of a smaller version of itself  Has one or more base cases

Recursive Definitions (Cont’d)

0! n! 3! 2! 1!

= = = = =

1 (By Definition!) n x (n – 1) ! If n > 0 3 x 2! 2 x 1! 1 x 0!

0! =

1 (Base Case!)

1! = 2! = 3! =

1 x 0! 2 x 1! 3 x 2!

= 1x1=1 = 2x1=2 = 3x2=6

Recursive Definitions (Cont’d) • Recursive algorithm  Algorithm that finds the solution to a given problem by reducing the problem to smaller versions of itself  Has one or more base cases  Implemented using recursive methods

• Recursive method  Method that calls itself

• Base case  Case in recursive definition in which the solution is obtained directly  Stops the recursion

Recursive Definitions (Cont’d) • General solution  Breaks problem into smaller versions of itself

• General case  Case in recursive definition in which a smaller version of itself is called  Must eventually be reduced to a base case

Recursive Definitions (Cont’d) • Directly recursive: a method that calls itself • Indirectly recursive: a 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: the case where every recursive call results in another recursive call

Tracing a Recursive Method • Recursive method  Logically, you can think of a recursive method having unlimited copies of itself  Every recursive call has its own • Code • Set of parameters • Set of local variables

Tracing a Recursive Method (Cont’d) • 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 call

Deg Recursive Methods • Understand problem requirements • Determine limiting conditions • Identify base cases

Deg Recursive Methods (Cont’d) • Provide direct solution to each base case • Identify general case(s) • Provide solutions to general cases in of smaller versions of general cases

Recursive Factorial Method

public static int fact(int num) { if (num = = 0) return 1; else return num * fact(num – 1); }

Recursive Factorial Method (Cont’d)

Figure 1: Execution path of fact(4)

Largest Value in Array

Figure 2: Array with six elements

Largest Value in Array (Cont’d) • •

• •

if the size of the list is 1 - the largest element in the list is the only element in the array else - to find the largest element in list[a]...list[b] a. find the largest element in list[a + 1]...list[b] and call it max b. compare list[a] and max if (list[a] >= max) the largest element in list[a]...list[b] is list[a] else the largest element in list[a]...list[b] is max

Largest Value in Array (Cont’d) public static int largest(int[] list, int lowerIndex, int upperIndex) { int max; if (lowerIndex == upperIndex) return list[lowerIndex]; else { max = largest(list, lowerIndex + 1, upperIndex); if (list[lowerIndex] >= max) return list[lowerIndex]; else return max; } }

Execution of largest(list, 0, 3)

Figure 3: Array with four elements

System.out.println(largest(list, 0, 3));

Execution of largest(list, 0, 3) (Cont’d)

Figure 4: Execution of largest(list, 0, 3)

Recursive Fibonacci

Recursive Fibonacci (Cont’d)

public static int rFibNum(int a, int b, int n) { if (n == 1) return a; else if (n == 2) return b; else return rFibNum(a, b, n -1) + rFibNum(a, b, n - 2); }

Recursive Fibonacci (Cont’d)

Figure 5: Execution of rFibNum(2, 3, 5)

Recursion and the Method Call Stack • 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

Recursion and the Method Call Stack (Cont’d)

Figure 6: Method calls on the program execution stack

Towers of Hanoi Problem with Three Disks

Figure 7: Tower of Hanoi Problem with three disks

Towers of Hanoi: Three Disk Solution

Figure 8: Tower of Hanoi Problem with three disks – Solution 1

Towers of Hanoi: Three Disk Solution (Cont’d)

Figure 9: Tower of Hanoi Problem with three disks – Solution 2

Towers of Hanoi: Recursive Algorithm

public static void moveDisks(int count, int needle1, int needle3, int needle2) { if (count > 0) { moveDisks(count - 1, needle1, needle2, needle3); System.out.println("Move disk " + count + " from needle " + needle1 + " to needle " + needle3 + ". "); moveDisks(count - 1, needle2, needle3, needle1); } }

Recursion or Iteration? • Two ways to solve particular problem  Iteration  Recursion

• Both iteration and recursion use a control statement  Iteration uses a repetition statement  Recursion uses a selection statement

Recursion or Iteration? (Cont’d) • 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 of processor time and memory space, but usually provides a more intuitive solution

Programming Example: Decimal to Binary

public static void decToBin(int num, int base) { if (num > 0) { decToBin(num / base, base); System.out.print(num % base); } }

Execution of decToBin(13, 2)

Figure 10: Execution of decToBin(13, 2)

Sierpinski Gaskets of Various Orders

Figure 11: Sierpinski Gaskets

Programming Example: Sierpinski Gasket • Input: non-negative integer indicating level of Sierpinski gasket • Output: triangle shape displaying a Sierpinski gasket of the given order • Solution includes:  Recursive method drawSierpinski  Method to find midpoint of two points

Programming Example: Sierpinski Gasket (Cont’d)

private void drawSierpinski(Graphics g, int lev,Point p1, Point p2, Point p3) { Point midP1P2; Point midP2P3; Point midP3P1; if (lev > 0) { g.drawLine(p1.x, p1.y, p2.x, p2.y); g.drawLine(p2.x, p2.y, p3.x, p3.y); g.drawLine(p3.x, p3.y, p1.x, p1.y); midP1P2 = midPoint(p1, p2); midP2P3 = midPoint(p2, p3); midP3P1 = midPoint(p3, p1); drawSierpinski(g, lev - 1, p1, midP1P2,midP3P1); drawSierpinski(g, lev - 1, p2, midP2P3, midP1P2); drawSierpinski(g, lev - 1, p3, midP3P1, midP2P3); } }

Programming Example: Sierpinski Gasket (Cont’d)

Figure 12: Sierpinski Gaskets: Recursion depth of 3

Lecture Summary • Recursive definitions • Recursive algorithms • Recursive methods • Base cases • General cases

Lecture Summary (Cont’d) • Tracing recursive methods • Deg recursive methods

• Varieties of recursive methods • Recursion vs. Iteration • Various recursive functions explored