- 表面上: A function that calls itself
- 实质上: Boil down a big problem to smaller ones
- 实现上:
- Base case: smallest problem to resolve
- Recursive rule: how to make the problem smaller
- Base case: F(0) = 0, F(1) = 1
- Recursive rule: F(n) = F(n-1) + F(n-2)
public int fibonacci(int n)
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return fibonacci(n-1) + fibonacci(n-2);