Category 1
What is a base case?
A base case in recursion is the condition that stops the recursive function from calling itself indefinitely. It defines the simplest instance of the problem, providing a direct answer without further recursion.
What structure is used to represent non-linear recursion?
a) Tree
b) Stack
c) Queue
d) Linked List
A. tree
What is the value of g(11) given the recursive function below?
g(x) = {
g(x - 3) + 1 if x > 0
3x otherwise
}
a) -3
b) -1
c) 0
d) 1
D. 1
Write a recursion for calculating n!, where we assume the factorial of negative integers is 1.
public class Factorial {
public static int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
}
What is the time complexity of generating all subsets with recursion?
a) O(n)
b) O(n!)
c) O(2ⁿ)
d) O(n²)
C. O(2ⁿ)
What is the value of h(13) given the recursive function below?
h(x) = {
h(x - 7) + 1 when x > 5
x when 0 ≤ x ≤ 5
h(x + 3) when x < 0
}
a) 1
b) 2
c) 3
d) 4
D. 4
Explain a solution to reverse a string using recursion.
public class ReverseString {
public static String reverse(String str) {
if (str.length() <= 1) return str;
return reverse(str.substring(1)) + str.charAt(0);
}
}
What type of memory does recursion use?
a) Heap
b) Stack
c) Register
d) Random Access Memory
What is the value of f(12, 6) given the recursive function below?
f(x, y) = {
f(x - y, y - 1) + 2 when x > y
x + y otherwise
}
9
Write a recursive formula and the base cases: Consider an n x n grid whose squares may have traps. It is not allowed to move to a square with a trap. Your task is to calculate the number of paths from the lower-left square to the upper-right square. You can only move right or up.
public class GridPaths {
static boolean[][] traps;
public static int countPaths(int x, int y) {
if (x < 0 || y < 0) return 0;
if (traps[x][y]) return 0;
if (x == 0 && y == 0) return 1;
return countPaths(x - 1, y) + countPaths(x, y - 1);
}
}
What technique is used to optimize recursion?
a) Loop Unrolling
b) Fragmentation
c) Memoization
d) Branch Prediction
C. Memoization
Write a recursive formula and the base cases: Your task is to count the number of ways to construct sum n by throwing a dice one or more times. Each throw produces an outcome between 1 and 6.
public class DiceSumWays {
public static int countWays(int sum) {
if (sum == 0) return 1;
if (sum < 0) return 0;
int ways = 0;
for (int i = 1; i <= 6; i++) {
ways += countWays(sum - i);
}
return ways;
}
}