Recursion & Backtracking — Chapter Quiz · Data Structures & Algorithms

Question 1

1

What is the role of a base case in a recursive function?

AIt improves time complexity from O(n) to O(log n)BIt is the condition that stops the recursion and returns a direct answer without further callsCIt memoizes intermediate resultsDIt prevents the function from being called with invalid arguments

Without a base case, recursion never terminates. The base case provides the simplest problem instance whose answer is known directly, anchoring the recursive descent.

Question 2

2

Why does V8 (Node.js) not support true tail-call optimisation (TCO) in practice?

ATCO is banned by the ECMAScript specificationBV8 removed TCO after an initial implementation because it broke stack traces and developer toolingCJavaScript is single-threaded, making TCO impossibleDTCO only works with async functions

ES2015 specified proper tail calls, and V8 shipped them behind a flag, but the feature was later disabled because accurate stack traces became unreliable. As of 2024 V8 does not perform TCO. Deep recursion in Node.js will still hit the default ~10,000-frame stack limit.

Question 3

3

The divide-and-conquer paradigm splits a problem into subproblems, solves them recursively, then:

ADiscards the results and recomputes from scratchBCaches all results in a global mapCCombines the subproblem solutions to form the overall answerDSorts the subproblems before combining

The three steps are: Divide, Conquer (recurse), Combine. Merge sort divides the array in two, sorts each half recursively, then merges the sorted halves. The merge step is the "combine".

Question 4

4

In a backtracking solution, what happens when the current partial solution violates a constraint?

AThe algorithm throws an exception and restartsBThe branch is pruned — the function returns immediately and undoes the last choiceCThe constraint is relaxed and the search continuesDA global flag is set and the loop skips future iterations

Backtracking prunes invalid branches early. The current choice is undone (the state is "un-chosen"), and the algorithm backtracks to try the next alternative. This avoids exploring the full exponential space.

Question 5

5

What is the time complexity of generating all permutations of an array of n distinct elements?

AO(n²)BO(2ⁿ)CO(n · n!)DO(n log n)

There are n! permutations, and each takes O(n) to copy/output. The total work is therefore O(n · n!). The recursive call tree itself has n! leaves.

Question 6

6

Every recursive algorithm can be converted to an iterative one using an explicit stack.

TTrueFFalse

Recursion uses the call stack implicitly. By managing your own stack data structure you can simulate that call stack iteratively, which also avoids the risk of V8's call-stack overflow.

Question 7

7

The number of distinct subsets of a set with n elements (the power set) is ___.

Each element is either included or excluded, giving two choices per element and 2ⁿ total subsets. Generating all subsets is therefore inherently exponential.

Question 8

8

Which of the following are good strategies to avoid call-stack overflow for deep recursion in Node.js? (Select all that apply)

Select all that apply.

AConvert the recursion to an iterative approach with an explicit stackBUse trampolining — wrap recursive calls in thunks and execute them in a loopCPass --stack-size=<bytes> to the node binary to increase the stack limitDUse async/await — it automatically eliminates stack growth

Iterative conversion, trampolining, and increasing Node's stack size are all valid workarounds. async/await does NOT prevent stack overflow for CPU-bound deep recursion — each await yields to the event loop but a tight synchronous recursive loop still consumes stack frames rapidly.

Test what you learned.

Recursion — Chapter Quiz