base case
The smallest input a recursive function answers directly, without calling itself again, which stops the recursion.
In more detail
For a factorial function the base case is n equal to zero or one. In dynamic programming tables, base cases are the first row and column filled before anything else. A missing or unreachable base case causes infinite recursion and, in Python, a RecursionError.
Related terms
- recursion — A technique where a function solves a problem by calling itself on a smaller version of the same problem.
- tabulation — Bottom-up dynamic programming: filling a table of subproblem answers in order from the base cases up, so each entry's inputs are ready before it.
Taught in
- Space, In-Place Work And The Call Stack — Algorithms & Data Structures for Working Engineers
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers
- Backtracking: Search With Pruning — Algorithms & Data Structures for Working Engineers
- Dynamic Programming: Memoisation And Tabulation — Algorithms & Data Structures for Working Engineers
- Functions, Return Values And Recursion — PCEP Certified Entry-Level Python Programmer (PCEP-30-02) Exam Prep
- Functions And Exceptions Sprint — PCEP Certified Entry-Level Python Programmer (PCEP-30-02) Exam Prep
References
- NIST Dictionary of Algorithms and Data Structures: recursion termination
- NIST Dictionary of Algorithms and Data Structures: recursion