Recursion definition
Recursion defines or solves a problem using smaller or simpler instances of the same problem.
Recursion in a picture
How it works
A recursive procedure handles a base case directly. In other cases it calls itself on inputs closer to a base case and combines the returned results as needed. The reduction and the base case together allow the procedure to finish.
Worked examples
Evaluate F(3) if F(0) = 1 and F(n) = 2F(n − 1).
F(1) = 2, F(2) = 4, and F(3) = 8.
Why is the base case needed?
It gives a direct answer and ends that chain of calls.
Does calling the same rule with the same input guarantee progress?
No. A terminating design needs a path to a base case.
Common mistake
Make sure every recursive call progresses toward a base case. A recursive formula alone can leave a value undetermined.
Quick check
Can recursion have two base cases?
Show answer
Yes.
What stops a recursive chain?
Show answer
A base case that returns without another recursive call.
Sources
Flashcard
Recursion
Reveal the definition
Recursion defines or solves a problem using smaller or simpler instances of the same problem.
Effortless Math. “Recursion.” Math Dictionary.
