# Lecture14

Views:

Category: Education

## Presentation Description

No description available.

## Presentation Transcript

### Lecture 14 Recursion:

1 Lecture 14 Recursion April 24, 2007 Prof. Kyu Ho Park

### Recursion:

2 Recursion ₪ Recursive Functions: It is one that calls itself. Example: 1, if n = 0 or 1 n! = n( n-1 )!, if n > 1 2! = 2(1!) = 2 3! = 3(2!) = 6 4! = 4(3!) = 4(6) = 24 5! = 5(4!) = 5(24) = 120 6! = 6(5!) = 6(120) = 720

### Factorial:

3 Factorial class TestRecursiveFactorial { public static void main( String[ ] args) { for( int i=0; i < 10; i++) System.out.println( i + “\t” + factorial(i)); } static long factorial( int n ) { if( n < 2) return 1; return n*factorial( n-1); } }

### Fibonacci Numbers:

4 Fibonacci Numbers ₪ Fibonacci Numbers 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 

### Recursive Fibonacci Function:

5 Recursive Fibonacci Function 1 class TestRecursiveFibonacci { 2 public static void main(String[] args) { 3 for (int i = 0; i < 13; i++) 4 System.out.println(i + "\t" + f(i)); 5 } 6 static long f(int n) { 7 if (n < 1) return 0; // base 8 if (n < 3) return 1; // base 9 return f(n-1) + f(n-2); // recursion 10 } 11 }

### Fibonacci’s Rabbit Problem:

6 Fibonacci’s Rabbit Problem

### Calling Trees :

7 Calling Trees 1 class TimeRecursiveFibonacci { 2 public static void main(String[] args) { 3 for (int n=30; n<=40; n++) { 4 long t0=System.currentTimeMillis(); 5 long m=f(n); 6 long t1=System.currentTimeMillis(); 7 System.out.println("f("+n+")="+m+"\ttime: "+(t1-t0)); 8 } 9 } 10 static long f(int n) { if( n < 1) return 0; if( n < 3) return 1; return f(n-1) + f(n-2); } 12 }

### Output:

8 Output f(30) = 832040 time: 78 f(31) = 1346269 time: 125 f(32) = 2178309 time: 188 f(33) = 3524578 time: 297 f(34) = 5702887 time: 468 f(35) = 9227465 time: 782 f(36) = 14930352 time: 1265 f(37) = 24157817 time: 1953 f(38) = 39088169 time: 3219 f(39) = 63245986 time: 5250 f(40) = 102334155 time: 8531

9 Execution Time

### Calling Tree for the Recursive Fibonacci method:

10 Calling Tree for the Recursive Fibonacci method

### Sequence of Execution:

11 Sequence of Execution 1. main() calls f(6) 2. f(6) calls f(5) 3. f(5) calls f(4) 4. f(4) calls f(3) 5. f(3) calls f(2) 6. f(2) returns 1 to f(3) 7. f(3) calls f(1) 8. f(1) returns 1 to f(3) 9. f(3) returns 1 + 1 = 2 to f(4) 10. f(4) calls f(2) 11. f(2) returns 1 to f(4) 12. f(4) returns 2 + 1 = 3 to f(5) 13. f(5) calls f(3) 14. f(3) calls f(2) 15. f(2) returns 1 to f(3) 16. f(3) calls f(1) 17. f(1) returns 1 to f(3) 18. f(3) returns 1 + 1 = 2 to f(5) 19. f(5) returns 3 + 2 = 5 to f(6) 20. f(6) calls f(4) 21. f(4) calls f(3) 22. f(3) calls f(2) 23. f(2) returns 1 to f(3) 24. f(3) calls f(1) 25. f(1) returns 1 to f(3) 26. f(3) returns 1 + 1 = 2 to f(4) 27. f(4) calls f(2) 28. f(2) returns 1 to f(4) 29. f(4) returns 2 + 1 = 3 to f(6) 30. f(6) returns 5 + 3 = 8 to main()

### TimeIterativeFibonacci:

12 TimeIterativeFibonacci 1 class TimeIterativeFibonacci { 2 public static void main(String[] args) { 3 for (int n = 30; n <= 40; n++) { 4 long t0=System.currentTimeMillis(); 5 long m=f(n); 6 long t1=System.currentTimeMillis(); 7 System.out.println("f(" + n + ") = " + m + " \ttime:” + (t1-t0));  8 }   9 }   10 static long f(int n) {   11 if (n<2) return n;   12 long f0=0, f1=1, f2=1;   13 for (int i=2; i<n; i++) {   14 f0 = f1;   15 f1 = f2;   16 f2 = f1 + f0;   17 }   18 return f2;   19 }   20 }

### Output:

13 Output f(30) = 832040 time: 0 f(31) = 1346269 time: 0 f(32) = 2178309 time: 0 f(33) = 3524578 time: 0 f(34) = 5702887 time: 0 f(35) = 9227465 time: 0 f(36) = 14930352 time: 0 f(37) = 24157817 time: 0 f(38) = 39088169 time: 0 f(39) = 63245986 time: 0 f(40) = 102334155 time: 0

### Storing instead of Recomputing :

14 Storing instead of Recomputing Iterative Function vs. Recursive Function The Iterative Function is faster than the Recursive one. The Recursive one is simpler. The Recursive one is slower since, it recomputes the same value many times.

### Temporary Storage :

15 Temporary Storage 1 class TimeStoredFibonacci { 2 public static void main(String[] args) { 3 for (int n = 30; n <= 40; n++) { 4 long t0 = System.currentTimeMillis(); 5 long m = Fibonacci.number(n); 6 long t1 = System.currentTimeMillis(); 7 System.out.println("f(" + n + ") = " + m + “ \ttime:” + ( t1-t0)); 8 } } } 12 class Fibonacci { 13 private static long[] fib = new long[100]; 14 private static int lastFibIndex = 2; 16 static { // class initializer 17 fib[1] = fib[2] = 1; 18 } 20 public static long number(int n) { 21 for (int i = lastFibIndex+1; i <= n; i++) 22 fib[i] = fib[i-1] + fib[i-2]; 23 if (n > lastFibIndex) lastFibIndex = n; 24 return fib[n]; 25 } 26 }

### Output:

16 Output f(30) = 832040 time: 31 f(31) = 1346269 time: 0 f(32) = 2178309 time: 0 f(33) = 3524578 time: 0 f(34) = 5702887 time: 0 f(35) = 9227465 time: 0 f(36) = 14930352 time: 0 f(37) = 24157817 time: 0 f(38) = 39088169 time: 0 f(39) = 63245986 time: 0 f(40) = 102334155 time: 0

### De Moivre Formula:

17 De Moivre Formula

### De Moivre Formula :

18 De Moivre Formula 1 class TestDeMoivre { 2 private static final double SR5=Math.sqrt(5); // 2.2360679774997896 3 private static final double PHI=(1+SR5)/2; // 1.6180339887498948 4 private static final double PSI=(1-SR5)/2; // -0.6180339887498948 6 public static void main(String[] args) { 7 for (int n = 0; n <= 10; n++) 8 System.out.println("f(" + n + ") = " + f(n)); 9 for (int n = 30; n <= 40; n++) { 10 long t0 = System.currentTimeMillis(); 11 long m = f(n); 12 long t1 = System.currentTimeMillis(); 13 System.out.println("f(" + n + ") = " + m + " \ttime: " +(t1-t0)); 14 } 15 } 17 static long f(int n) { 18 return (long)((Math.pow(PHI,n) - Math.pow(PSI,n))/SR5); 19 } 20 }

### Output:

19 Output f(0) = 0 f(1) = 1 f(2) = 1 f(3) = 2 f(4) = 3 f(5) = 5 f(6) = 8 f(7) = 13 f(8) = 21 f(9) = 34 f(10) = 55 f(30) = 832040 time: 0 f(31) = 1346269 time: 0 f(32) = 2178309 time: 0 f(33) = 3524578 time: 0 f(34) = 5702887 time: 0 f(35) = 9227465 time: 0 f(36) = 14930352 time: 0 f(37) = 24157817 time: 0 f(38) = 39088169 time: 0 f(39) = 63245986 time: 0 f(40) = 102334155 time: 0

### The Towers of Hanoi:

20 The Towers of Hanoi No disk may be placed upon a smaller disk.

21 Solution

### Towers of Hanoi:

22 Towers of Hanoi 1 class HanoiTowers { 2 public static void main(String[ ] args) { 3 int numTowers = 3; 4 if (args.length>0) numTowers=Integer.parseInt(args[0]); 5 print(numTowers, 'A', 'B', 'C'); 6 } 7 8 static void print(int n, char x, char y, char z) { 9 // move n disks from peg x to peg y using peg z: 10 if (n == 1) System.out.println(x + " --> " + y); // base 11 else { 12 print(n-1, x, z, y); // recursion 13 System.out.println(x + " --> " + y); 14 print(n-1, z, y, x); // recursion 15 } 16 } 17 }

### Iterative Binary Search :

23 Iterative Binary Search //The Binary Search 1 public class TestBinarySearch { 3 public static void main(String[] args) { 4 int[] a = {22, 33, 44, 55, 66, 77, 88, 99}; 5 System.out.println("search(a," + 55 + "): " + search(a, 55)); 6 System.out.println("search(a," + 50 + "): " + search(a, 50)); 7 } 9 static int search(int[] a, int x) { 10 int p = 0, q = a.length-1; 11 while (p <= q) { // search the segment a[p..q] 12 int i = (p+q)/2; // index of element in the middle 13 if (a[i] == x) return i; 14 if (a[i] < x) p = i+1; // search upper half 15 else q = i-1; // search lower half 16 } 17 return -p-1; // not found 18 } 19 }

### Recursive Binary Search Algorithm:

24 Recursive Binary Search Algorithm ۩Algorithm

25

### Printing Permutation:

26 Printing Permutation public class Permutations { public static void main(String[] args){ String s = "ABC"; if (args.length > 0) s = args[0]; print(s); } public static void print(String s) { print(new StringBuffer(s), 0); } private static void print(StringBuffer s, int k) { // print all permutations of s that leave s[0]..s[k-1] invariant: if (k == s.length()-1) System.out.println(s); // base else for (int i=k; i<s.length(); i++) { swap(s, k, i); print(s, k+1); // recursion swap(s, k, i); } } private static void swap(StringBuffer s, int i, int j) { if (i == j) return; char ch = s.charAt(i); s.setCharAt(i, s.charAt(j)); s.setCharAt(j, ch); } }

### Indirect Recursion:

27 Indirect Recursion ۩Direct recursion: The function calls itself directly. ۩Indirect recursion: A chain of function calls forms a loop of length greater than one. Mutual recursion: Two functions call each other sin2θ = 2 sinθ cosθ, cos2θ = 1-2(sinθ)2

### Indirect Recursion:

28 Indirect Recursion class TestTrig { public static void main(String[] args) { for (double x = 0.0; x < 1.0; x += 0.1) System.out.println(sin(x) + "\t" + Math.sin(x)); for (double x = 0.0; x < 1.0; x += 0.1) System.out.println(cos(x) + "\t" + Math.cos(x)); } static double sin(double x) { if (-0.01 < x && x < 0.01) return x - x*x*x/6; // base return 2*sin(x/2)*cos(x/2); // recursion } static double cos(double x) { if (-0.01 < x && x < 0.01) return 1.0 - x*x/2; // base return 1 - 2*sin(x/2)*sin(x/2); // recursion } }