Recursion
Introduced| English |
|---|
| Recursion/rɪˈkɜːʃn/ |
| base case/beɪs keɪs/ |
| recursive case/rɪˈkɜːsɪv keɪs/ |
| unwind/ʌnˈwaɪnd/ |
A method that calls itself
- Recursion 递归 is when a method calls itself to solve a smaller version of the same problem.
- Every recursion needs two parts: a base case 基准情形 and a recursive case 递归情形.
- The base case stops the recursion — a small input the method answers directly.
- The recursive case calls the method again on a smaller input.
The base case
- Without a base case, a method calls itself forever — a
StackOverflowError. - The base case handles the smallest input without another call.
- Example:
factorial(0)returns1directly — no more calls. - Always check: does every path eventually reach the base case?
The recursive case
- The recursive case does a little work, then calls itself on a smaller input.
factorial(n)returnsn * factorial(n - 1)— the input shrinks by one each call.- Each call waits for the smaller call to return before finishing.
- The calls stack up, hit the base case, then unwind 回退 back to the top.
How the calls stack
factorial(3)→3 * factorial(2)→3 * (2 * factorial(1))→3 * (2 * (1 * factorial(0))).factorial(0)returns1; then the stack unwinds:1, 1, 2, 6.- Each call keeps its own copy of the parameters until it returns.
- Tracing a recursion means following the calls down, then the returns up.
Every recursion needs a base case that stops it — and each recursive call must move TOWARD that base case (a smaller input). Miss the base case, or call on the same or a larger input, and the method recurses forever until a StackOverflowError. Trace by following calls down to the base case, then the returns back up.
sum(n) = 1 + 2 + … + n by recursion:
- Base case:
if (n == 0) return 0; - Recursive case:
return n + sum(n - 1); sum(3)→3 + sum(2)→3 + (2 + sum(1))→ … →6.
Recursion is a method calling itself on a smaller input. It needs a base case (stops directly, no more calls) and a recursive case (does a little work, then recurses on a smaller input). Calls stack down to the base case, then unwind back up. Miss the base case and you get a StackOverflowError.
factorial(3) unwinds from the base case up
fact(0) returns 1 (base case); each parent multiplies: 1, 1, 2, 6.
A recursive method is one that...
Recursion = a method calling itself.
The base case is...
The base case stops the recursion.
A recursion with no reachable base case causes...
It recurses forever until the stack overflows.
The recursive case must call itself on...
Each call must shrink toward the base case.
If factorial(0)=1 and factorial(n)=n*factorial(n-1), what is factorial(3)?
3 * 2 * 1 * 1 = 6.
Each recursive call keeps its own copy of its parameters until it returns.
Calls stack independently, then unwind.