Recursion and Recurrence Relations Flashcards
1
Q
What is recursion?
A
A function calling itself to solve a smaller instance of the same problem.
2
Q
What is a base case in recursion?
A
The condition that stops the recursion to prevent infinite loops.
3
Q
What is a recurrence relation?
A
An equation defining a function in terms of smaller inputs.
4
Q
Solve the recurrence relation: T(n) = T(n/2) + O(1).
A
O(log n) using the recurrence tree method.
5
Q
What is tail recursion?
A
A recursive function where the recursive call is the last operation, allowing for optimization into iteration.
5
Q
What is the recurrence relation for Merge Sort?
A
T(n) = 2T(n/2) + O(n).
6
Q
What is the Master Theorem?
A
A formula to solve recurrence relations in divide-and-conquer algorithms.
