Base Case and Recursive Case

Part of: Recursion

What Is Recursion? Recursion is when a method calls itself to solve a smaller version of the same problem. Every recursive method needs two ingredients: - A base case : the simplest input where the answer is known directly, with no further calls. This stops the recursion. - A recursive case : where the method calls itself on a smaller input, moving toward the base case. If you forget the base case, or the recursive case never shrinks the problem, you get infinite recursion and a StackOverflowError. A Classic Example: Factorial The factorial n! = n (n-1) ... 1, and 0! = 1. Notice that n! = n (n-1)!. That self-reference is the recursive case. When we call factorial(4): - factorial(4) returns 4 factorial(3) - factorial(3) returns 3 factorial(2) - factorial(2) returns 2 factorial(1) - factorial(1) hits the base case and returns 1 Then the results multiply back up: 2 1=2, 3 2=6, 4 6=24. Why the Base Case Matters The base case is the exit door . Each recursive call must make progress toward it, here, n always decreases by 1, so we are guaranteed to reach n <= 1. Without that shrinking, recursion never ends. Recursion vs. Iteration Anything a loop can do, recursion can do, and vice versa.

Challenge: Recursive Factorial