All Flashcards
What is the definition of Recursion?
A method of solving a problem where the solution depends on solutions to smaller instances of the same problem. A function calls itself with a smaller version of the original problem.
What is the definition of Base Case?
A condition in a recursive method that terminates the recursive calls and provides a direct solution.
What is the definition of Recursive Call?
When a function calls itself with a modified version of the original problem, usually after checking the base case.
What is the definition of Binary Search?
A search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.
What is the definition of Merge Sort?
An efficient, general-purpose, comparison-based sorting algorithm that divides an array into two halves, sorts each half, and then merges the sorted halves back together.
What are the differences between recursion and iteration?
Recursion: Solves problems by breaking them into smaller, self-similar subproblems. Can be more elegant for some problems. | Iteration: Solves problems by repeating a block of code until a condition is met. Generally more efficient in terms of speed and memory.
What are the differences between linear search and binary search?
Linear Search: Checks each element sequentially. Works on unsorted arrays. | Binary Search: Repeatedly divides the search interval in half. Requires a sorted array.
What are the key differences between iterative and recursive binary search?
Iterative Binary Search: Uses loops to narrow the search space. More efficient in terms of memory usage. | Recursive Binary Search: Calls itself with smaller sub-arrays. Can be more concise and easier to read for some programmers.
What does the following code output?
java
public int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n-1);
}
}
System.out.println(factorial(4));
24
Identify the error in the following code:
java
public int factorial(int n) {
return n * factorial(n-1);
}
Missing base case, which will cause a stack overflow error.
What does the following code output?
java
public void traverseArray(int[] array, int index) {
if (index == array.length) {
return;
}
System.out.println(array[index]);
traverseArray(array, index + 1);
}
int[] arr = {1, 2, 3};
traverseArray(arr, 0);
1 2 3
What does the following code output?
java
public int binarySearch(int[] array, int target, int low, int high) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (array[mid] == target) {
return mid;
} else if (target < array[mid]) {
return binarySearch(array, target, low, mid - 1);
} else {
return binarySearch(array, target, mid + 1, high);
}
}
int[] arr = {2, 4, 6, 8, 10};
System.out.println(binarySearch(arr, 6, 0, arr.length - 1));
2
Identify the potential issue in the following binary search code:
java
int mid = (low + high) / 2;
Integer overflow can occur if low + high exceeds the maximum integer value. Using mid = low + (high - low) / 2; is a safer alternative.
Predict the output of the following code:
java
public int mystery(int n) {
if (n <= 0) {
return 0;
} else {
return n + mystery(n - 2);
}
}
System.out.println(mystery(5));
9
What is the output of the following code?
java
public int recursiveMethod(int num) {
if (num == 0)
return 1;
else
return num * recursiveMethod(num - 1);
}
System.out.println(recursiveMethod(3));
6
What is the output of the following code?
java
public int method(int num) {
if (num == 5)
return 5;
else
return num + method(num + 1);
}
System.out.println(method(2));
14
What is the output of the following code?
java
public int method(int num) {
if (num == 0)
return 0;
else
return 1 + method(num / 2);
}
System.out.println(method(8));
4
What is the output of the following code?
java
public int method(int num) {
if (num == 0)
return 0;
else
return 1 + method(num - 1);
}
System.out.println(method(4));
4