Recursion Quiz — A-Level Computer Science

Question 1

A recursive function is defined to calculate the greatest common divisor (GCD) of two non-negative integers, $a$ and $b$, using the Euclidean algorithm. The function is given by:$$ \text{def gcd(a, b):} \\ \quad \text{if b == 0:} \\ \qquad \text{return a} \\ \quad \text{else:} \\ \qquad \text{return gcd(b, a \% b)} $$What is the sequence of recursive calls for $gcd(48, 18)$?

Question 2

Consider a scenario where a recursive function is used to traverse a binary tree. If the tree has a depth of $N$ and each node requires a fixed amount of memory for its stack frame, what is the approximate space complexity of this recursive traversal in the worst-case scenario?

Question 3

A programmer is tasked with converting a recursive algorithm for calculating the $n^{th}$ Fibonacci number into an iterative solution. The recursive definition is:$ \text{F(n) = F(n-1) + F(n-2)} \\ \text{F(0) = 0} \\ \text{F(1) = 1} $Which of the following iterative approaches would be the most efficient in terms of time and space complexity for large values of $n$?

Question 4

Consider a recursive function that calculates the power of a number $x$ to an integer exponent $n$ ($x^n$). The function is defined as:$$ \text{def power(x, n):} \\ \quad \text{if n == 0:} \\ \qquad \text{return 1} \\ \quad \text{elif n > 0:} \\ \qquad \text{return x * power(x, n-1)} \\ \quad \text{else:} \\ \qquad \text{return 1 / (x * power(x, -n-1))} $$What is the value returned by $power(2, -3)$?

Question 5

A recursive function is used to perform a depth-first search (DFS) on a graph. In the context of recursion depth, what is the primary factor that determines the maximum number of active function calls on the call stack during the DFS traversal?

Recursion — Quiz

Practice Questions