Mastering Recursion: Interview-Ready Quiz Quiz

1. Q1: Base Case

   What is the primary purpose of a base case in a recursive function?

   1. To improve the function's performance significantly.
   2. To define the initial input values.
   3. To prevent the function from calling itself indefinitely, stopping the recursion.
   4. To handle any potential errors that may arise.

2. Q2: Tail Recursion

   Which of the following best describes a tail-recursive function?

   1. A function that calls itself multiple times within a single iteration.
   2. A function where the recursive call is the very last operation performed in the function.
   3. A function that does not require a base case.
   4. A function that is optimized for handling strings.

3. Q3: Stack Overflow

   What is a common cause of a 'stack overflow' error when using recursion?

   1. Insufficient memory allocated to the heap.
   2. Reaching the maximum integer value.
   3. Exceeding the maximum recursion depth allowed by the system.
   4. Using incorrect data types.

4. Q4: Factorial Recursion

   What is the time complexity of a recursive function to calculate the factorial of a number 'n'?

   1. O(log n)
   2. O(n)
   3. O(n^2)
   4. O(2^n)

5. Q5: Fibonacci

   Why is the straightforward recursive implementation of the Fibonacci sequence inefficient?

   1. Because it uses iterative methods.
   2. Because it recalculates the same Fibonacci numbers multiple times.
   3. Because it cannot be implemented using recursion.
   4. Because it requires very large stack memory.

6. Q6: Memoization

   What is memoization, and how does it improve the performance of recursive functions?

   1. A technique to increase the size of the stack.
   2. A technique for storing the results of expensive function calls and returning the cached result when the same inputs occur again.
   3. A technique to reduce the number of variables used in the function.
   4. A technique that forces the function to run in parallel.

7. Q7: Permutations

   Which algorithm is most suitable for generating all permutations of a given string?

   1. Depth-first search (DFS) using recursion.
   2. Breadth-first search (BFS) using a queue.
   3. Dynamic programming.
   4. Greedy Algorithm

8. Q8: Subset Generation

   What programming technique is commonly used to find all possible subsets of a set?

   1. Iterative looping.
   2. Recursion with backtracking.
   3. Using a hash table.
   4. Linear Search

9. Q9: Backtracking

   What is the core concept behind backtracking algorithms?

   1. Exploring the solution space by iteratively improving the current best solution.
   2. Exploring the solution space incrementally, abandoning paths when they don't lead to a solution.
   3. Dividing the problem into smaller subproblems and solving them independently.
   4. Randomly exploring the solution space to find a near-optimal solution.

10. Q10: N-Queens

    Which of the following problems can be effectively solved using a backtracking algorithm?

    1. Sorting a list of numbers.
    2. Finding the shortest path in a graph.
    3. The N-Queens problem.
    4. Calculating the area of a circle.

11. Q11: Sudoku Solver

    In a recursive Sudoku solver, what typically represents the base case?

    1. Finding an empty cell to fill.
    2. Filling a row or column.
    3. The Sudoku grid is fully filled and valid.
    4. The Sudoku grid is invalid.

12. Q12: Tree Traversal

    Which tree traversal algorithm is naturally implemented using recursion?

    1. Breadth-first search (BFS).
    2. Depth-first search (DFS).
    3. Dijkstra's Algorithm.
    4. Binary Search

13. Q13: Optimizing Recursion

    Besides memoization, what's another common technique to optimize recursive functions, particularly tail-recursive ones?

    1. Using a global variable.
    2. Tail call optimization.
    3. Increasing the stack size.
    4. Using a different programming language.

14. Q14: Space Complexity

    What is the space complexity associated with a non-tail-recursive function?

    1. O(1) constant space.
    2. O(log n) logarithmic space.
    3. O(n) linear space, due to the call stack.
    4. O(n^2) quadratic space.

15. Q15: Recursive Case

    In a recursive function, what does the 'recursive case' primarily do?

    1. Defines the stopping condition.
    2. Calls the function itself with modified arguments, working towards the base case.
    3. Returns a constant value.
    4. Handles any errors encountered.