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
20! = 1;
n! = n x (n-1)!; n > 0 base case
/stopping condition
- factorial of n (n的乘阶)
ComputeFactorial.java
1 | /* |
- Check Point
18.3 Case Study: Computing Fibonacci Numbers
- Word
- medieval 中世紀的
- originate 發明vt =create
- considerable 相當大的
- successive 連續的
- Content
- Fibonacci rule
1
2
3fib(0) = 0;
fib(1) = 1;
fib(index) = fib(index - 2) + fib(index - 1); index >= 2; - recursive way
1
2
3
4
5
6if (index == 0)
return 0;
else if (index == 1)
return 1;
else
return fib(index - 1) + fib(index - 2);
- Fibonacci rule
ComputeFibonacci.java
1 | /* |
- Check Point
18.4 Problem Solving Using Recursion
- Word
- sip 一小口 一啖
- palindrome 迴文,對稱單詞(dad mom)
- Content
- think recursively
1 | public static void drinkCoffee(Cup cup) { |
1 | public static void nPrintln(String message, int times) { |
RecursivePalindromeUsingSubstring.java
1 | /* |
Check Point
18.5 Recursive Helper Methods
Content
- recursive helper method
private static boolean isPalindrome(String s, int low, int highg)
RecursivePalindrome.java
1 | /* |
18.5.1 Recursive Selection Sort
RecursiveSelectionSort.java
1 | /* |
18.5.2 Recursive Binary Search
RecursiveBinarySearch.java
1 | /* |
18.6 Case Study: Finding the Directory Size
DirectorySize.java
1 | /* |
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 | import java.util.Scanner; |
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 | /* |