Recursion 1
Which word is used to describe a non-recursive sorting or searching algorithm?
Iterative
What is the output of the following recursive method call: factorial(4)?
public static int factorial(int n) {
if (n == 0) return 1;
else return n * factorial(n-1);
}
a) 24; b) 12; c) 16; d) 8
24
What case is constantly repeated until the base case is reached?
a) Constant case
b) Infinite case
c) Case case
d) Recursive case
Recursive case
public class DigitSum {
public static int sumOfDigits(int n) {
if (n == 0) { return 0; }
else { return n % 10 + sumOfDigits(n / 10); }
}
public static void main(String[] args) {
int number = 12345;
System.out.println(sumOfDigits(number)); }
}
What is the function and output of the code?
This Java method recursively calculates the sum of digits of a given integer and the output is 15.
What is the stopping condition in a recursive function?
Which of the following is an example of a base case in a recursive method?
A) A method call to itself with modified parameters
B) A conditional statement that returns a value without further recursion
C) A loop that iterates a fixed number of times
D) A mathematical operation involving the method's parameters
A conditional statement that returns a value without further recursion
What is parallel recursion?
This concept, often used in recursive algorithms, allows multiple recursive calls to be executed in parallel, typically used in divide-and-conquer algorithms.
public static int binarySearch(int[] arr, int target, int left, int right) {
if (left > right) { return -1; } // Base case: target not found
//Fill in the missing code
if (arr[mid] == target) { return mid; }
else if (arr[mid] > target) { return binarySearch(arr, target, left, mid - 1); }
else { return binarySearch(arr, target, mid + 1, right); }
}
int mid = left + (right - left) / 2;
Any recursive solution can be replicated through the use of an iterative approach. True or False?
True
_____ track the progress of a recursive function. Fill in the blank.
Parameter values
In the following recursive method, how many times will fibonacci be called when fibonacci(5) is executed?
public static int fibonacci(int n) {
if (n == 0) return 0;
else if (n == 1) return 1;
else return fibonacci(n-1) + fibonacci(n-2);
}
A) 5
B) 8
C) 9
D) 15
Which of the following sorting algorithms is recursive?
Selection Sort
Insertion Sort
Merge Sort
Heap Sort
Merge Sort