Free Practice Quiz Question List

05 Recursion Online Quiz Questions

Use this free practice quiz with 20 questions to review 05 Recursion, test your knowledge, and prepare for your next test or exam.

20 questions

Choose one

1 point

Which role does the base case play in a correct recursive algorithm?

A
It divides the input into equal-sized parts.
B
It provides a directly known answer and stops further calls.
C
It stores every previously computed result.
D
It reverses the most recent choice.

True or false

1 point

True or false: Recursive calls return in last-in, first-out order because they are managed by the call stack.

A
True
B
False

Written response

1 point

What is the name of the part of a recursive algorithm that reduces the problem to one or more smaller instances of the same problem?

Fill in the blank

1 point

Complete the two role descriptions: The reduces the problem and makes another recursive call, while the provides a direct answer and prevents further calls.

Choose one

1 point

The function $sumTo(n)$ makes one recursive call on $n-1$ and performs constant additional work. What is its running time?

A
O(n)
B
O(log n)
C
O(n log n)
D
O(2^n)

Choose all

1 point

Select all statements that correctly describe the recursive binary-search implementation in the material.

A
Its running time is O(log n).
B
It always examines every element in the array.
C
Its recursive call-stack space is O(log n).
D
It has exponential running time because each call makes two recursive calls.

True or false

1 point

True or false: In backtracking, the algorithm must undo a choice after the recursive exploration of that choice finishes.

A
True
B
False

Fill in the blank

1 point

The recurrence $T(n)=2T(n/2)+O(n)$ is associated with merge sort. Its running time is .

Choose all

1 point

Select all consequences of applying the memoized Fibonacci implementation from the material to compute $fib(n)$ .

A
The time complexity becomes O(n).
B
The time complexity remains O(2^n).
C
The memoization table requires O(n) additional storage.
D
Memoization guarantees O(1) total space.

Open ended

1 point

Explain how to design and evaluate a correct recursive algorithm. Your answer must discuss the base case, recursive case, progress toward termination, call-stack behavior, and the main complexity considerations.

Choose one

1 point

Which algorithm in the material is described as having commonly expressed running time O(2^n) because it repeatedly solves overlapping subproblems?

A
Memoized Fibonacci
B
Direct recursive Fibonacci without memoization
C
Iterative factorial
D
Recursive binary search

Written response

1 point

What is the auxiliary-space complexity of the iterative factorial implementation in the material? Enter the bound in Big-O notation.

Choose one

1 point

Which part of a recursive algorithm directly handles a simplest input and prevents further recursive calls?

A
The recursive case
B
The base case
C
The call-stack frame
D
The memoization case

Choose one

1 point

When recursive function calls return after reaching a base case, which order does the call stack follow?

A
First-in, first-out
B
Random order based on input size
C
Last-in, first-out
D
All frames return simultaneously

Choose one

1 point

A recursive binary search examines the middle of a sorted array and discards half of the remaining range on each call. What is its running time?

A
$O(\log n)$
B
$O(n)$
C
$O(n\log n)$
D
$O(2^n)$

Choose one

1 point

A recursive traversal processes each node of a tree once. Which complexity description is correct, where $n$ is the number of nodes and $h$ is the tree height?

A
$O(1)$
B
$O(n)$ for both time and stack space
C
$O(\log n)$ for both time and stack space
D
$O(n)$ time and $O(h)$ stack space

Choose one

1 point

A direct recursive Fibonacci algorithm is changed to use memoization. What is the resulting time and additional-storage complexity?

A
It changes the algorithm to constant time and uses no extra memory.
B
It reduces the time to $O(n)$ and uses $O(n)$ additional storage.
C
It reduces the time to $O(\log n)$ and uses $O(1)$ additional storage.
D
It increases the time to $O(n^2)$ but removes the recursion stack.

True or false

1 point

True or false: The straightforward recursive and iterative implementations of factorial can both take $O(n)$ time, but the iterative version can use $O(1)$ auxiliary space while the recursive version uses $O(n)$ call-stack space.

A
True
B
False

Written response

1 point

The recursive function is defined by $S(n)=n+S(n-1)$ with $S(0)=0$ . What value does $S(4)$ return?

Written response

1 point

What algorithmic technique stores the results of previously computed recursive subproblems so repeated subproblems can be answered without recomputation?