Recursion – Data Structures and Algorithms:
Exam-Ready Questions and Answers
LATEST UPDATE 2026/2027 | PREMIUM ACADEMIC EDITION
Exam 06 of 40 | Unit code: DSA-06 | Questions: 6 | Total marks: 30 | Answer ALL questions
Question 1: [4 marks]
Define recursion. Explain the roles of the base case and the recursive case.
Answer:
Recursion is a technique in which a function solves a problem by calling itself on smaller instances
of the same problem. The base case stops the recursion by returning a direct answer. The
recursive case reduces the problem and calls the function again. Without a reachable base case
the recursion never terminates and causes a stack overflow.
Question 2: [5 marks]
Write a recursive function for n! and state its time and space complexity.
Answer:
def fact(n):
if n <= 1:
return 1
return n * fact(n - 1)
Time O(n) (n calls). Space O(n) because of the n stack frames.
Question 3: [6 marks]
Why is the naive recursive Fibonacci function inefficient? How can its complexity be improved?
Answer:
fib(n) = fib(n-1) + fib(n-2) recomputes the same subproblems many times, so the number of calls
n n
grows exponentially (O(2 ) as an upper bound, about 1.618 ).
With memoization (caching results) or an iterative loop each value is computed once, giving O(n)
time; the iterative version needs only O(1) space.
Question 4: [5 marks]
State the recurrence and the minimum number of moves for the Tower of Hanoi with n discs.
How many moves are needed for 4 discs?
Answer:
n
T(n) = 2T(n − 1) + 1 with T(1) = 1, which solves to T(n) = 2 − 1.
4
For 4 discs: 2 − 1 = 15 moves.
Page 1 Data Structures and Algorithms • Exam 06
Exam-Ready Questions and Answers
LATEST UPDATE 2026/2027 | PREMIUM ACADEMIC EDITION
Exam 06 of 40 | Unit code: DSA-06 | Questions: 6 | Total marks: 30 | Answer ALL questions
Question 1: [4 marks]
Define recursion. Explain the roles of the base case and the recursive case.
Answer:
Recursion is a technique in which a function solves a problem by calling itself on smaller instances
of the same problem. The base case stops the recursion by returning a direct answer. The
recursive case reduces the problem and calls the function again. Without a reachable base case
the recursion never terminates and causes a stack overflow.
Question 2: [5 marks]
Write a recursive function for n! and state its time and space complexity.
Answer:
def fact(n):
if n <= 1:
return 1
return n * fact(n - 1)
Time O(n) (n calls). Space O(n) because of the n stack frames.
Question 3: [6 marks]
Why is the naive recursive Fibonacci function inefficient? How can its complexity be improved?
Answer:
fib(n) = fib(n-1) + fib(n-2) recomputes the same subproblems many times, so the number of calls
n n
grows exponentially (O(2 ) as an upper bound, about 1.618 ).
With memoization (caching results) or an iterative loop each value is computed once, giving O(n)
time; the iterative version needs only O(1) space.
Question 4: [5 marks]
State the recurrence and the minimum number of moves for the Tower of Hanoi with n discs.
How many moves are needed for 4 discs?
Answer:
n
T(n) = 2T(n − 1) + 1 with T(1) = 1, which solves to T(n) = 2 − 1.
4
For 4 discs: 2 − 1 = 15 moves.
Page 1 Data Structures and Algorithms • Exam 06
