Unit 3: Recursion and Advanced Techniques - Practice Quiz

1 What is recursion in programming?

2 What is the main purpose of a base condition in recursion?

3 Which problem is commonly solved by using the recursive relation ?

4 When designing a recursive solution, the original problem is usually reduced to what?

5 Which technique is a classic recursive example?

6 Which modern technique avoids repeatedly solving the same recursive subproblems?

7 When a function calls itself directly, what type of recursion is used?

8 Function A calls function B, and function B calls function A. What does this demonstrate?

9 In tail recursion, where does the recursive call appear?

10 Which statement describes non-tail recursion?

11 Where are active recursive function calls generally stored?

12 What error may occur when recursion creates too many active calls?

13 What is a common advantage of recursion?

14 What is a common disadvantage of recursive programming?

15 What does a backtracking algorithm usually do after a choice leads to an invalid solution?

16 How many permutations are possible for three distinct elements?

17 What is the goal of the Combination Sum problem?

18 In the N-Queens problem, which queens attack each other?

19 How is the next value generated while checking whether a number is happy?

20 What property must the numeric parts of a sum string satisfy?

21 Consider the recursive function:

F(n) = 1 when n = 0, and F(n) = n + F(n - 1) otherwise.

What value is returned by F(4)?

22 A recursive function is intended to compute for non-negative integers:

power(a, n) = a * power(a, n - 1)

Which base condition makes the function correct?

23 A recursive binary search is called on a sorted array of elements. In the worst case, approximately how many times can the search range be halved before it becomes empty?

24 A direct recursive Fibonacci implementation repeatedly solves the same subproblems. Which technique most directly improves it while preserving its recursive structure?

25 Function A calls function B, function B calls function C, and function C calls function A. What type of recursion does this call structure represent?

26 Which function demonstrates direct recursion?

27 Which recursive return statement is tail-recursive, assuming acc stores the partial result?

28 Why is return n * factorial(n - 1) classified as non-tail recursion?

29 A recursive function makes one call with n - 1 until n == 0, and each call stores only a constant amount of local data. What is its auxiliary stack-space complexity?

30 For traversing a very deep tree, what is the main practical risk of using recursive depth-first search instead of an explicit stack?

31 A backtracking algorithm places values into positions and discovers that the current partial assignment violates a constraint. What should it do next?

32 Which change most effectively prunes a backtracking search without removing valid solutions?

33 How many distinct permutations can be formed from the characters in AABC?

34 In a swap-based recursive permutation algorithm, what must happen after returning from the recursive call for a chosen position?

35 Given candidates [2, 3, 6, 7], where each candidate may be reused, which set contains all unique combinations whose sum is ?

36 In a Combination Sum backtracking algorithm where candidates may be reused, which recursive index should be passed after choosing candidate i?

37 When placing a queen at row r and column c, which previously placed queen creates a diagonal conflict?

38 A row-by-row N-Queens solver stores occupied columns and diagonals in sets. Which pair of expressions can identify the two diagonals of position (r, c)?

39 A happy number repeatedly replaces a number with the sum of the squares of its digits until reaching . What is the smallest happy number greater than ?

40 A sum string can be split into numbers such that every number after the first two equals the sum of the previous two. Which split correctly proves that 122436 is a sum string?

41 Consider a recursive procedure that makes two calls on an input of half the original size and performs constant local work: , with . Assuming no memoization, which pair correctly describes its total running time and maximum recursion depth?

42 A function uses if (n == 1) return; as its only base condition and otherwise calls itself with n / 2 using integer division. Which replacement guarantees termination for every integer input?

43 A power function computes an even exponent using power(x, n/2) * power(x, n/2) without storing the first result. For restricted to powers of two, what are its time complexity and recursion depth?

44 A language has no tail-call optimization, but a deeply recursive state machine must avoid native stack overflow while preserving recursive control flow. Which transformation best achieves this?

45 Consider A(n) = 0 for and otherwise A(n) = 1 + B(n-1). Also, B(n) = 0 for and otherwise B(n) = 1 + A(\lfloor n/2 \rfloor). What are the value returned by A(20) and the maximum number of simultaneously active calls, including the base-case call?

46 Which implementation is tail-recursive, assuming ordinary eager evaluation?

47 Quicksort is modified to recurse only on the smaller partition and process the larger partition by updating bounds inside a loop. What worst-case bounds does this guarantee for auxiliary call-stack space and running time?

48 A depth-first traversal explores a tree with branching factor and maximum depth . Which statement accurately compares a recursive implementation with an iterative implementation using an explicit stack?

49 A combination-search algorithm sorts candidates and stops its loop when currentSum + candidate[i] > target. Under which condition is this pruning rule logically valid?

50 A backtracking solver builds assignments for variables, each with possible values. A feasibility test costing is executed at every recursion-tree node. With no effective pruning, what is the tightest asymptotic upper bound on running time?

51 For the multiset , how many distinct full-length permutations exist, and which loop condition correctly prevents duplicate generation after sorting?

52 Using one-based indexing, what is the nd lexicographic permutation of ?

53 Candidates are $[2,3,5]`, each may be reused any number of times, and combinations differing only by order are identical. How many combinations sum to $10$?

54 A recursive Combination Sum solver allows unlimited reuse by recursing with the same candidate index. Which input property can make the recursion nonterminating even when the target is finite?

55 In a bitmask N-Queens solver, cols, diagL, and diagR mark columns attacked in the current row, and full has its lowest bits set. Which expression computes available positions, and how are diagonal masks advanced after choosing bit p?

56 On a board with zero-based indices, queens have been placed at , , and . Which columns remain legal for a queen in row ?

57 A happy number repeatedly replaces a number by the sum of the squares of its decimal digits until reaching or entering a cycle. What is the smallest happy number strictly greater than ?

58 A sum string can be partitioned into at least three decimal numbers such that every number after the first two equals the sum of its two predecessors. For 199100199, which initial pair produces a valid complete partition?

59 When testing all possible first and second numbers of a sum string, which validation rule correctly handles leading zeros and termination?

60 Identical glasses of capacity are arranged in rows. Overflow from each glass is divided equally between the two glasses directly below it. If units are poured into the top glass, how much water is retained in the glass at row , column , using zero-based indices?