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.
26 cards · basic cards · AI-written, checked twice. Edit anything.
- What is recursion?
- A technique where a function calls itself to solve smaller instances of a problem
- What is a base case in recursion?
- The condition that stops further recursive calls
- What is a recursive case?
- The part of a function that calls itself with a smaller or simpler input
- What happens if a recursive function has no base case?
- It results in infinite recursion, eventually causing a stack overflow
- What is the call stack's role in recursion?
- It tracks each function call's state, unwinding as calls return
- What is a classic example of a recursive algorithm?
- Computing a factorial, or traversing a tree
- What is the time complexity of a naive recursive Fibonacci function?
- O(2^n), exponential, due to repeated redundant calculations
- What technique improves recursive Fibonacci's efficiency by storing previously computed results?
- Memoization
- What is memoization?
- Caching the results of expensive function calls to avoid redundant computation
- What is tail recursion?
- A recursive call that is the last operation performed in a function, allowing some compilers to optimize it
- What is tail call optimization?
- 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?
- A tree, since each subtree is itself a smaller tree
- What is the relationship between recursion and iteration?
- Any recursive algorithm can be rewritten iteratively, often using an explicit stack
- What is a recursive tree traversal?
- Visiting nodes of a tree by recursively visiting children, such as in preorder, inorder, or postorder
- What is mutual recursion?
- Two or more functions that call each other in a recursive cycle
FlashKeepers