Data Structures, unit: Recursion. Core concepts, terminology, and worked-example cues a college student meets for this unit, building on prior units without repeating them. Front: a term, concept, or short problem cue. Back: the definition, explanation, or answer.
38 cards · basic cards · AI-written, checked twice. Edit anything.
- What is recursion?
Show answer
A technique where a function calls itself to solve smaller instances of a problem- What is a base case in recursion?
Show answer
The condition that stops further recursive calls- What is a recursive case?
Show answer
The part of a function that calls itself with a smaller or simpler input- What happens if a recursive function has no base case?
Show answer
It results in infinite recursion, eventually causing a stack overflow- What is the call stack's role in recursion?
Show answer
It tracks each function call's state, unwinding as calls return- What is a classic example of a recursive algorithm?
Show answer
Computing a factorial, or traversing a tree- What is the time complexity of a naive recursive Fibonacci function?
Show answer
O(2^n), exponential, due to repeated redundant calculations- What technique improves recursive Fibonacci's efficiency by storing previously computed results?
Show answer
Memoization- What is memoization?
Show answer
Caching the results of expensive function calls to avoid redundant computation- What is tail recursion?
Show answer
A recursive call that is the last operation performed in a function, allowing some compilers to optimize it- What is tail call optimization?
Show answer
A compiler technique that reuses the current stack frame for a tail-recursive call, avoiding stack growth- What is an example of a naturally recursive data structure?
Show answer
A tree, since each subtree is itself a smaller tree- What is the relationship between recursion and iteration?
Show answer
Any recursive algorithm can be rewritten iteratively, often using an explicit stack- What is a recursive tree traversal?
Show answer
Visiting nodes of a tree by recursively visiting children, such as in preorder, inorder, or postorder- What is mutual recursion?
Show answer
Two or more functions that call each other in a recursive cycle
FlashKeepers