0%

CHAPTER 18 Recursion

18.1 Introduction

  • 單詞
  • elegant 優雅的
  • lead to 獲得
  • intuitive 直觀的
  • depict 描繪
  • integration 整合
  • propagation 宣傳,波及
  • Content
    • recursion for search word problem
    • H-trees

18.2 Case Study: Computing Factorials

  • 單詞
    • factorial 階乘的
    • decrement 减少
    • spawn 生成
    • manner 方式
    • converge into 匯成
    • infinite recursion into StackOverflowError
    • direct recursion && indirect recursion
  • Content
    • factorial of n (n的乘阶)
      1
      2
      0! = 1;
      n! = n x (n-1)!; n > 0
    • base case / stopping condition

ComputeFactorial.java

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
/*

⇒ java java-c18/ComputeFactorial.java
Enter a nonnegative integer: 3
Factorial of 3 is 6

*/

import java.util.Scanner;

public class ComputeFactorial {
public static void main(String[] args) {
System.out.print("Enter a nonnegative integer: ");
Scanner input = new Scanner(System.in);
int n = input.nextInt();
System.out.println("Factorial of " + n + " is " + factorial(n));
}

public static long factorial(int n) {
if (n == 0)
return 1;
else
return n * factorial(n - 1);
}
}

  • Check Point

18.3 Case Study: Computing Fibonacci Numbers

  • Word
    • medieval 中世紀的
    • originate 發明vt =create
    • considerable 相當大的
    • successive 連續的
  • Content
    • Fibonacci rule
      1
      2
      3
      fib(0) = 0;
      fib(1) = 1;
      fib(index) = fib(index - 2) + fib(index - 1); index >= 2;
    • recursive way
      1
      2
      3
      4
      5
      6
      if (index == 0)
      return 0;
      else if (index == 1)
      return 1;
      else
      return fib(index - 1) + fib(index - 2);

ComputeFibonacci.java

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
/*

⇒ java ComputeFibonacci
Enter an index for a Fibonacci number: 4
The Fibonacci number at index 4 is 3

*/


import java.util.Scanner;

public class ComputeFibonacci {
public static void main(String[] args) {
System.out.print("Enter an index for a Fibonacci number: ");
Scanner input = new Scanner(System.in);
int index = input.nextInt();
System.out.println("The Fibonacci number at index "
+ index + " is " + fib(index));
}

public static long fib(long index) {
if (index == 0)
return 0;
else if (index == 1)
return 1;
else
return fib(index - 1) + fib(index - 2);
}
}
  • Check Point

18.4 Problem Solving Using Recursion

  • Word
    • sip 一小口 一啖
    • palindrome 迴文,對稱單詞(dad mom)
  • Content
    • think recursively
1
2
3
4
5
6
public static void drinkCoffee(Cup cup) {
if (!cup.isEmpty()) {
cup.takeOnesip();
drinkCoffee(cup);
}
}
1
2
3
4
5
6
7
public static void nPrintln(String message, int times) {
// The base case is: time == 0
if (times >= 1) {
System.out.println(message);
nPrintln(message, times - 1);
}
}

RecursivePalindromeUsingSubstring.java

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
/*
⇒ java RecursivePalindromeUsingSubstring
Is moon a pailindrome? false
Is noon a pailindrome? true
Is aba a pailindrome? true
Is ab a pailindrome? false
*/

public class RecursivePalindromeUsingSubstring {
public static boolean isPalindrome(String s) {
if (s.length() <= 1)
return true;
else if (s.charAt(0) != s.charAt(s.length() -1))
return false;
else
return isPalindrome(s.substring(1,s.length()-1));
}

public static void main(String[] args) {
System.out.println("Is moon a pailindrome? "
+ isPalindrome("moon"));
System.out.println("Is noon a pailindrome? "
+ isPalindrome("noon"));
System.out.println("Is aba a pailindrome? "
+ isPalindrome("aba"));
System.out.println("Is ab a pailindrome? "
+ isPalindrome("ab"));
}
}

Check Point

18.5 Recursive Helper Methods

Content

  • recursive helper method
    • private static boolean isPalindrome(String s, int low, int highg)

RecursivePalindrome.java

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
31
32
33
34
35
/*
⇒ java RecursivePalindrome
Is moon a pailindrome? false
Is noon a pailindrome? true
Is aba a pailindrome? true
Is ab a pailindrome? false
*/

public class RecursivePalindrome {
public static boolean isPalindrome(String s) {
return isPalindrome(s, 0, s.length() - 1);
}

// recursive helper method
private static boolean isPalindrome(String s, int low, int highg) {
if (high <= low)
return true;
else if (s.charAt(low) != s.charAt(high))
return false;
else
return isPalindrome(s, low + 1, high - 1);
}

public static void main(String[] args) {
System.out.println("Is moon a pailindrome? "
+ isPalindrome("moon"));
System.out.println("Is noon a pailindrome? "
+ isPalindrome("noon"));
System.out.println("Is aba a pailindrome? "
+ isPalindrome("aba"));
System.out.println("Is ab a pailindrome? "
+ isPalindrome("ab"));
}
}

18.5.1 Recursive Selection Sort

RecursiveSelectionSort.java

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
⇒ java RecursiveSelectionSort
0.0
1.0
2.0
33.0
*/

public class RecursiveSelectionSort {
public static void main(String[] args) {
double[] list = {33, 2, 0, 1};
sort(list);
for (int i = 0; i < 4; i++)
System.out.println(list[i]);
}

public static void sort(double[] list) {
// sort the entire list
sort(list, 0, list.length - 1);
}

// low, smallest value position should be at [most left]
// indexOfMin, new found position that smallest value is at
// min, new found minimum value is min
// 「變量名的含義」是非常重要
private static void sort(double[] list, int low, int high) {
if (low < high) {
// Find the smallest number and its index in list
int indexOfMin = low;
double min = list[low];
// begin with the position after low
for (int i = low + 1; i <= high; i++) {
if (list[i] < min) {
min = list[i];
indexOfMin = i;
}
}
// Swap the smallest in list
list[indexOfMin] = list[low];
list[low] = min;
// Sort the remaining list[low +1 ...]
sort(list, low + 1, high);
}
}
}

RecursiveBinarySearch.java

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
31
32
33
34
35
36
37
38
39
40
41
/*
⇒ java RecursiveBinarySearch
0 : 0
1 : 5
2 : 10
3 : 144
4 : 555
-6 : 1000
*/

public class RecursiveBinarySearch {
public static void main(String[] args) {
// must be in increasing order
int[] list = {0, 5, 10, 144, 555};
for (int i = 0; i < list.length; i++)
System.out.println(recursiveBinarySearch(list, list[i])
+ " : " + list[i]);
System.out.println(recursiveBinarySearch(list, 10000)
+ " : " + 1000);

}

public static int recursiveBinarySearch(int[] list, int key) {
int low = 0;
int high = list.length - 1;
return recursiveBinarySearch(list, key, low, high);
}

private static int recursiveBinarySearch(int[] list, int key,
int low, int high) {
if (low > high)
return -low - 1;
int mid = (low + high) / 2;
if (key < list[mid])
return recursiveBinarySearch(list, key, low, mid - 1);
else if (key == list[mid])
return mid;
else
return recursiveBinarySearch(list, key, mid + 1, high);
}
}

18.6 Case Study: Finding the Directory Size

DirectorySize.java

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
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
56
57
58
59
60
61
62
63
/*
⇒ java DirectorySize
Enter a directory or a file: /Users/zijim/note/source/_posts/java-c18
FOLDER: java-c18
FILE: .DS_Store
FOLDER: test
FILE: RecursiveSelectionSort.java~
FILE: ComputeFactorial.java~
FILE: ComputeFibonacci.java~
FILE: DirectorySize.java~
FILE: ComputeFactorial.java
FILE: RecursiveSelectionSort.class
FILE: ComputeFactorial.class
FILE: ComputeFibonacci.class
FILE: DirectorySize.class
FILE: RecursivePalindrome.java
FILE: DirectorySize.java
FILE: RecursiveSelectionSort.java
FILE: RecursivePalindromeUsingSubstring.java
FILE: RecursiveBinarySearch.java~
FILE: RecursiveBinarySearch.java
FILE: RecursivePalindrome.class
FILE: RecursivePalindromeUsingSubstring.java~
FILE: RecursivePalindrome.java~
FILE: RecursivePalindromeUsingSubstring.class
FILE: ComputeFibonacci.java
FILE: RecursiveBinarySearch.class
27464 bytes
*/

import java.io.File;
import java.util.Scanner;

public class DirectorySize {
public static void main(String[] args) {
System.out.print("Enter a directory or a file: ");
Scanner input = new Scanner(System.in);
String directory = input.nextLine();
System.out.println(getSize(new File(directory))
+ " bytes");
}

public static long getSize(File file) {
long size = 0;
if (file.isDirectory()) {
System.out.println("FOLDER: " + file.getName());

// `listFiles()` will list all files and folders
File[] files = file.listFiles();

for (int i = 0; files != null && i < files.length; i++) {
size += getSize(files[i]);
}
}
else {
System.out.println("FILE: " + file.getName());
// file object not exsit, then it will return 0
size += file.length();
}

return size;
}
}

18.7 Case Study: Tower of Hanoi

word

  • inherently recursive nature 天性地 递归 性质
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // move n disks 
    // from `fromTower` to `toTower` with assistance of `auxTower`
    void moveDisks(int n, char fromTower, char toTower, char auxTower) {
    if (n == 1) // stopping condition
    Move disk 1 from fromTower to the toTower;
    else {
    moveDisks(n - 1, fromTower, auxTower, toTower);
    Move disk n from the fromTower to the toTower;
    moveDisks(n - 1, auxTower, toTower, fromTower);
    }
    }

TowerOfHanoi.java

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
31
32
33
34
35
36
37
38
import java.util.Scanner;

public class TowerOfHanoi {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("Enter number of disks: ");
int n = input.nextInt();
// Find the solution recursively
System.out.println("The moves are:");
moveDisks(n, 'A', 'B', 'C');
}

public static void moveDisks(int n, char fromTower,
char toTower, char auxTower) {
if (n == 1)
System.out.println("Move disk " + n + " from " +
fromTower + " to " + toTower);
else {
moveDisks(n - 1, fromTower, auxTower, toTower);
System.out.println("Move disk " + n + " from " +
fromTower + " to " + toTower);
moveDisks(n - 1, auxTower, toTower, fromTower);
}
}
}

/*
Enter number of disks: 3
The moves are:
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B
*/

18.8 Case Study: Fractals(不規則圖形)

  • geometrical 幾何的
  • equilateral 等邊的

SierpinskiTriangle.java

18.9 Recursion vs. Iteration

  • repetition 重複
  • bear 承擔
  • substantial 大量的
  • overhead 開銷
  • nature 性質
  • intuitive 直觀的

18.10 Tail Recursion

  • incorporate 包含
  • overload 超載與
  • auxiliary 輔助的 /ɔɡ’zɪlɪəri/
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
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
56
57
58
/*

⇒ java java-c18/ComputeFactorial.java
Enter a nonnegative integer: 3
Factorial of 3 is 6

import java.util.Scanner;

public class ComputeFactorial {
public static void main(String[] args) {
System.out.print("Enter a nonnegative integer: ");
Scanner input = new Scanner(System.in);
int n = input.nextInt();
System.out.println("Factorial of " + n + " is " + factorial(n));
}

public static long factorial(int n) {
if (n == 0)
return 1;
else
return n * factorial(n - 1);
}
}

*/

import java.util.Scanner;

public class ComputeFactorialTailRecursion {

public static void main(String[] args) {
System.out.print("Enter a nonnegative integer: ");
Scanner input = new Scanner(System.in);
int n = input.nextInt();
System.out.println("Factorial of " + n + " is " + factorial(n));
}

public static long factorial(int n) {
return factorial(n, 1);
}

private static long factorial(int n, int result) {
if (n == 0)
return result;
else
return factorial(n - 1, n * result);
}

}

/*
⇒ java ComputeFactorialTailRecursion
Enter a nonnegative integer: 3
Factorial of 3 is 6

1 x 2 x 3 = 6
*/