What is recursion?
Recursion solves a problem by having a function call itself on a smaller or simpler version of that problem.
Study 2 Recursion with 12 free online flashcards. Review key terms, definitions, and concepts with this interactive flashcard deck.
What is recursion?
Recursion solves a problem by having a function call itself on a smaller or simpler version of that problem.
What is a base case?
A base case is a condition whose answer is known directly and that stops further recursive calls.
What is a recursive case?
A recursive case reduces the problem and calls the same function on a smaller instance.
What does progress mean in recursion?
Each recursive call must move closer to a base case, usually by reducing the input or advancing through a structure.
How does recursion use the call stack?
The call stack stores active function calls in last-in, first-out order, so the most recent recursive call returns first.
What is recursion depth?
Recursion depth is the maximum number of simultaneously active recursive calls. It determines the stack space used by the recursion.
What is the cost of decrease-by-one recursion?
A decrease-by-one recurrence has the form T(n)=T(n−1)+O(1), giving O(n) running time and typically O(n) call depth.
Why is recursive binary search O(logn)?
Binary search follows T(n)=T(n/2)+O(1), so its running time and recursion depth are both O(logn).
Why is naive recursive Fibonacci inefficient?
Naive recursive Fibonacci recomputes the same subproblems many times, producing exponential running time. Memoization reduces the running time to O(n).
What recurrence describes merge sort?
Merge sort divides the array, recursively sorts both halves, and merges them. Its recurrence is T(n)=2T(n/2)+O(n), giving O(nlogn) time.
Why is binary-tree traversal O(n)?
A tree traversal uses the empty tree as its base case and recursively processes child subtrees. Visiting each node once gives O(n) running time.
What is backtracking?
Backtracking recursively explores a choice, then undoes it before trying another choice. Pruning invalid partial solutions can reduce the search.
A progressive guide to how computers encode numbers, text, images, and sound as binary data, including the trade-offs and limits of digital representation.
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 progressive guide to tree structure, binary-tree traversals, binary search tree operations, deletion, balancing, and the way tree height determines time and space costs.
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.