What is recursion?
Recursion is a technique in which a function calls itself on a smaller or simpler version of the original problem.
Study 05 Recursion with 12 free online flashcards. Review key terms, definitions, and concepts with this interactive flashcard deck.
What is recursion?
Recursion is a technique in which a function calls itself on a smaller or simpler version of the original problem.
What is the purpose of a base case?
The base case gives an answer directly and prevents further recursive calls.
What does a recursive case do?
The recursive case reduces the problem, calls the function on the smaller instance, and combines the returned result when necessary.
What does a recursive call add to the call stack?
Each active recursive call creates a stack frame containing parameters, local state, and a return location.
In what order do recursive calls return?
Recursive calls return in last-in, first-out order: the most recent call returns before its caller resumes.
What is factorial recursion's call-stack space?
For the recursive factorial implementation, the maximum call-stack depth is n+1, so its call-stack space is O(n).
What is decrease-and-conquer?
Decrease-and-conquer makes one recursive call on a smaller problem, often of size n−1 or n/2.
What are binary search's recursive time and stack bounds?
Binary search has recurrence T(n)=T(n/2)+O(1), giving O(logn) time and O(logn) recursive stack space.
What is the complexity of recursive tree traversal?
A recursive tree traversal processes each node once, taking O(n) time and O(h) stack space, where h is tree height.
What is the core cycle of backtracking?
Backtracking applies a choice, recursively explores the resulting state, then undoes the choice before trying another option.
Why is naive recursive Fibonacci exponential?
Naive recursive Fibonacci takes commonly expressed exponential time, O(2n), because it repeatedly recomputes overlapping subproblems.
How does memoization improve recursive Fibonacci?
Memoization stores computed subproblem results. For Fibonacci, it reduces time to O(n) and uses O(n) additional storage.
A focused set of flashcards covering Python variables, data types, expressions, control flow, functions, input, output, and common programming practices.
Learn how Boolean expressions, logical operators, and conditional structures let programs make reliable decisions, including how to handle boundaries, branch order, and testing.
A structured guide to the main data structures, their operations, efficiency trade-offs, representations, and practical selection criteria.
A 14-question quiz on trees, binary trees, traversals, recursive algorithms, and binary search trees. The questions progress from foundational concepts to applied reasoning about structure, complexity, and BST operations.
A structured guide to comparison-based sorting algorithms, their complexity, stability, memory use, and practical selection criteria.
A progression through how data is organized, searched, exposed through software interfaces, and managed through abstraction layers in modern computer systems.
A medium-difficulty quiz on integrating problem definition, representation, algorithms, complexity analysis, testing, correctness, ethical evaluation, and documentation in a computer science capstone.
A practical guide to integrating problem definition, data representation, modular programming, algorithms, complexity analysis, testing, correctness, and ethical evaluation into a responsible computer science capstone.
This quiz covers process management, context switching and scheduling, multitasking, traps and interrupts, and RISC-V privilege transitions.