All Flashcards
What is the core idea behind recursion?
Breaking down a large problem into smaller, self-similar subproblems.
Why is a base case essential in a recursive function?
To prevent infinite loops by providing a terminating condition.
What happens if a recursive function lacks a proper base case?
It results in an infinite loop, potentially causing a stack overflow error.
What is the prerequisite for using binary search on an array?
The array must be pre-sorted.
How does binary search improve search efficiency compared to linear search?
By repeatedly dividing the search space in half, eliminating a large portion of the array from consideration with each step.
What are the two main steps in merge sort?
Divide and Conquer. The divide step splits the array, and the conquer step sorts and merges the halves.
What is the base case for merge sort's recursive calls?
When the array has only one element, it is already sorted.
What is the role of the merge() function in merge sort?
To combine two sorted arrays into a single sorted array.
What are the trade-offs between recursion and iteration?
Recursion can lead to more concise code but may be slower due to function call overhead. Iteration is often faster but can result in more verbose code.
What is the purpose of the index parameter in the recursive array traversal example?
It keeps track of the current position within the array being processed.
What are the general steps for writing a recursive function?
- Identify the base case(s). 2. Define the recursive call to solve a smaller subproblem. 3. Ensure the recursive call moves towards the base case.
What are the steps of the binary search algorithm?
- Find the middle element. 2. Compare the target to the middle element. 3. If target equals middle, return index. 4. If target is less than middle, search the left half. 5. If target is greater than middle, search the right half. 6. Repeat until found or search space is empty.
What are the main steps of the merge sort algorithm?
- Divide the array into two halves. 2. Recursively sort the two halves. 3. Merge the sorted halves.
How is recursion applied in real-world scenarios?
In algorithms like tree traversal, graph searching, and in compilers for parsing code.
How is binary search applied in real-world scenarios?
Searching for a word in a dictionary, finding a contact in a sorted list, or locating data in a sorted database index.
How is merge sort applied in real-world scenarios?
Used in external sorting (sorting large datasets that don't fit in memory), and as a building block in other algorithms.