Recursion Fundamentals u0026 Backtracking Essentials Quiz Quiz

Explore the core principles of recursion and backtracking with scenario-driven questions designed to deepen understanding of function calls, stack usage, base cases, and solution space exploration. Evaluate your grasp of recursive algorithms and essential backtracking strategies to improve your problem-solving skills in computer science.

1. Identifying Proper Base Cases in Recursion

   Which of the following base cases correctly terminates a recursive function designed to calculate the factorial of a positive integer n?

   1. When n == 2, return n
   2. When n == 0, return 0
   3. When n u003C 0, return 1
   4. When n == 1, return 1

   Explanation: The correct base case for factorial is 'When n == 1, return 1' because factorial of 1 is defined as 1 and stops recursion. Returning 0 when n == 0 is incorrect, as factorial of 0 is 1. Returning 1 for n u003C 0 is invalid since factorial isn't defined for negative numbers. Returning n when n == 2 does not halt the recursion properly, as factorial for 2 should follow the same pattern as for other positive integers.

2. Understanding Backtracking Algorithm Output

   Given a backtracking algorithm for generating all possible subsets of the set {1, 2}, which of the following accurately represents the complete output?

   1. [[], [1], [1, 2]]
   2. [[], [1], [2], [1, 2]]
   3. [[], [1, 2], [2, 1]]
   4. [[1], [2], [1, 2]]

   Explanation: Backtracking generates all possible combinations including the empty set, so '[[], [1], [2], [1, 2]]' is correct. The option missing the empty set is incomplete. '[[], [1, 2], [2, 1]]' lists [2, 1], which is not a distinct subset but a permutation. '[[], [1], [1, 2]]' leaves out the subset [2], so it's also inaccurate.

3. Recognizing Stack Overflow in Recursion

   What is a common cause for a stack overflow error when running recursive code to calculate Fibonacci numbers?

   1. The function uses an incorrect return type
   2. The recursion depth is intentionally limited
   3. The recursive function lacks a base case for n == 0 or n == 1
   4. The parameters are passed by reference instead of value

   Explanation: A missing base case allows recursion to continue indefinitely, leading to stack overflow. Choosing the wrong return type may cause compile-time errors, but not stack overflow. Limiting recursion depth prevents the error rather than causing it. Passing parameters by reference impacts memory usage but does not inherently cause stack overflow.

4. Tracing Recursive Function Calls

   If a function recurses to sum digits of an integer n (e.g., n = 1234), which sequence of calls happens for the initial input?

   1. sumDigits(1234), sumDigits(12), sumDigits(124), sumDigits(234)
   2. sumDigits(1234), sumDigits(1), sumDigits(2), sumDigits(3)
   3. sumDigits(1234), sumDigits(234), sumDigits(34), sumDigits(4)
   4. sumDigits(1234), sumDigits(123), sumDigits(12), sumDigits(1)

   Explanation: Recursive digit-sum typically removes the last digit each step, so the function is called with 1234, then 123, 12, and 1. The other options skip digits or rearrange the order incorrectly, or attempt calls with non-sequential values. Only the first option shows correct decreasing order of calls by dividing by 10.

5. Choosing Efficient Backtracking Structure

   When solving a Sudoku puzzle with backtracking, what is the main reason for choosing to try all numbers from 1 to 9 in each empty cell?

   1. To exhaustively explore all possible configurations for a solution
   2. Because all cells in Sudoku must be filled in sequential order
   3. Because only odd numbers can be valid in Sudoku
   4. To minimize the number of recursive function calls

   Explanation: Backtracking in Sudoku tries all options to ensure every valid possibility is considered for each cell. Assuming only odd numbers are valid contradicts Sudoku rules. While efficient implementations prune branches, the method does not inherently minimize the number of calls. Cells do not have to be filled strictly sequentially; order can vary.