Free Practice Quiz Question List

2 Recursion Online Quiz Questions

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

20 questions

Choose one

1 point

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

A
It always makes two recursive calls
B
It stops further recursive calls for a known input
C
It converts recursion into iteration
D
It increases the problem size

Choose one

1 point

Using the recursive definition of factorial in the material, what value does $factorial(4)$ return?

A
4
B
16
C
24
D
120

Choose one

1 point

A recursive binary search makes one call on approximately half the input and performs constant additional work. What is its running time?

A
$O(1)$
B
$O(\log n)$
C
$O(n)$
D
$O(n \log n)$

Choose all

1 point

Which steps are part of a sound process for designing a recursive solution? Select all that apply.

A
Define precisely what the subproblem should return
B
Ensure every recursive call moves closer to a base case
C
Increase the problem size at each recursive call
D
Combine the recursive result with the current computation
E
Ignore the cost of calls and call-stack depth

Choose all

1 point

In which situations is recursion often a clear or natural choice? Select all that apply.

A
Processing a tree structure
B
A divide-and-conquer algorithm
C
A backtracking search with branching choices
D
A simple loop whose input may be extremely large
E
A situation where stack space is severely limited

True or false

1 point

Recursive function calls are removed from the call stack in last-in, first-out order.

A
True
B
False

True or false

1 point

Python generally replaces a tail-recursive function's current stack frame instead of adding a new one.

A
True
B
False

Written response

1 point

For the material's correct $countdown(n)$ function called as $countdown(4)$ , how many numbers are printed before the base case is reached?

Fill in the blank

1 point

The condition for which a recursive function's answer is known directly is its .

Fill in the blank

1 point

The maximum number of simultaneously active stack frames during a recursive computation is called .

Open ended

1 point

Explain how mathematical induction can establish the correctness of the recursive factorial function for every nonnegative integer.

Choose one

1 point

A preorder traversal recursively visits the root and then the left and right subtrees. For a binary tree with $n$ nodes, what is its running time?

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

Choose one

1 point

In the recursive function sum_from(a, i), which condition serves as the base case for summing the elements from index i through the end of the array?

A
i == len(a)
B
i == 0 for every input
C
a[i] == 0
D
i is increased by 2

Choose one

1 point

Given the recursive function countdown(n) that prints returning n after calling countdown(n - 1), what sequence is printed after calling countdown(3) reaches its base case?

A
returning 3, returning 2, returning 1
B
returning 1, returning 2, returning 3
C
returning 0, returning 1, returning 2
D
No returning messages are printed

Choose one

1 point

A merge sort implementation recursively sorts two halves of an array and then merges the halves in linear time. What is the resulting asymptotic running time?

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

Choose one

1 point

The naive recursive Fibonacci function makes repeated calls for the same inputs. Which change described in the material reduces its running time to $O(n)$ ?

A
Store previously computed results with memoization
B
Remove both recursive calls and return 0
C
Increase the recursion depth limit
D
Make each recursive call use the same argument

True or false

1 point

True or false: In Python, making a recursive call the final operation of a function generally prevents additional stack frames from accumulating.

A
True
B
False

Written response

1 point

Using the recursive definition of factorial in the material, what value does factorial(5) return?

Written response

1 point

What proof method establishes recursive algorithm correctness by proving a base case and then showing that correctness for smaller inputs implies correctness for the current input?

Written response

1 point

Consider a linked-list function that returns 0 for an empty node and otherwise returns 1 + length(node.next). What recursion pattern does this function use?