Study guides & original practice
Recursion and base cases practice
A recursive function solves a problem by calling itself on a smaller or simpler problem. A reachable stopping condition is as important as the recursive step.
By ExamCat · Original study lesson · Published September 24, 2026
Understand the method
Trace both descent and return. Each call can wait for another call’s result, so the answer is often assembled while calls return. A base case must match the valid input domain, and each recursive call must move toward it.
Worked example, step by step
For nonnegative integers, define factorial(0) = 1 and factorial(n) = n × factorial(n − 1). Evaluate factorial(4).
- Expand: factorial(4) = 4 × factorial(3).
- Continue through 3 × factorial(2) and 2 × factorial(1).
- The call reaches factorial(0) = 1.
- Return upward: 1, then 1, then 2, then 6, then 24. Thus factorial(4) = 24.
A mistake to watch for
A stopping condition does not help if the input moves away from it. This definition also needs input validation or an expanded specification for negative integers; blindly subtracting one will never reach zero.
Try it yourself: three questions
Write an answer before opening the explanation. For calculations, keep your units and intermediate steps; for concepts, state the reason for your choice.
1. What is factorial(1) under this definition?
Show answer and explanation
1 × factorial(0) = 1.
2. What is wrong with factorial(n) calling factorial(n + 1) for positive n?
Show answer and explanation
It moves away from the zero base case, so the recursive chain does not terminate as intended.
3. Does recursion always use less memory than iteration?
Show answer and explanation
No. Pending calls can consume stack space. The exact behavior depends on the algorithm, runtime and optimization.
Build your next practice session
Mark the first step where your reasoning differed from the explanation. Turn that step into a question, answer it without looking, then change one condition in the example and explain what would change. A correct guess is a reason to revisit the method.
Use the free flashcard maker for your own question-and-answer pairs, or bring your course material into PDF-to-flashcards practice.
Further reading
OpenStax: data structures and algorithms provides textbook background. The worked scenario and practice questions on this page were written independently for ExamCat.
Related lessons
Practice your own class material
Generate flashcards, notes and quizzes from your lecture notes in Exam Cat.
Try 7 days free ↗Yearly plan: 7 days free, then $39.99/year. Cancel before the trial ends to avoid a charge.
APUSH study guide · Biology study guide · APUSH practice · All study tools