Recursion
Introduced| English | Meaning |
|---|---|
| Recursion/rɪˈkɜːʃn/ | Solving a problem through calls to the same routine, with reachable stopping cases for terminating computations. |
| base case/beɪs keɪs/ | A case that can be solved directly and stops further recursive calls. |
| recursive case/rɪˈkɜːsɪv keɪs/ | The part of a recursive definition or algorithm that reduces a problem by invoking the same process on a smaller or simpler case. |
| unwind/ʌnˈwaɪnd/ | unwind |
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?
Merge sort calls itself on each half, then merges the sorted halves
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...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Recursion = a method calling itself.
The base case is...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The base case stops the recursion.
A recursion with no reachable base case causes...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
It recurses forever until the stack overflows.
The recursive case must call itself on...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Each call must shrink toward the base case.
If factorial(0)=1 and factorial(n)=n*factorial(n-1), what is factorial(3)?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
3 * 2 * 1 * 1 = 6.
Each recursive call keeps its own copy of its parameters until it returns.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Calls stack independently, then unwind.