Recursion & Backtracking Quiz

8 questions10 minPass: 60%+10 XP on first pass

Base cases, the call stack, recursion trees and the choose–explore–unchoose template.

Free account · see your score, answers and explanations, earn XP

Question 1
What happens if a recursive function has no base case?
It returns 0It recurses forever until a stack overflowIt runs onceThe compiler adds one automatically

Question 2

What does this print?

def f(n):
    if n <= 1:
        return 1
    return n * f(n - 1)
print(f(5))

Question 3
How many subsets does a set of 4 distinct elements have?
Question 4
How many permutations does [1, 2, 3] have?
Question 5
What are the three steps of the backtracking template?
Choose, explore, unchooseSort, search, returnDivide, conquer, mergePush, pop, peek
Question 6
Why must you append a COPY of path (path[:] / new ArrayList<>(path)) to the results?
Copies are fasterpath keeps changing; without a copy every result points to the same listThe results list only accepts copiesTo sort the result
Question 7
Naive recursive Fibonacci fib(n) = fib(n−1) + fib(n−2) has roughly what time complexity?
O(n)O(n²)O(2ⁿ)O(log n)
Question 8Select all that apply
To avoid duplicate combinations when the input has repeated numbers (Subsets II), you… (select all that apply)
Sort the input firstSkip nums[i] when it equals nums[i−1] at the same recursion levelUse a stack instead of recursionReverse the input