Recursion

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) returns 1 directly — 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) returns n * 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) returns 1; 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.