Revise later
SpaceTo flip
If confident
All Flashcards
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
What is the core idea behind recursion?
Breaking down a large problem into smaller, self-similar subproblems.
Why is a base case essential in a recursive function?
To prevent infinite loops by providing a terminating condition.
What happens if a recursive function lacks a proper base case?
It results in an infinite loop, potentially causing a stack overflow error.
What is the prerequisite for using binary search on an array?
The array must be pre-sorted.
How does binary search improve search efficiency compared to linear search?
By repeatedly dividing the search space in half, eliminating a large portion of the array from consideration with each step.
What are the two main steps in merge sort?
Divide and Conquer. The divide step splits the array, and the conquer step sorts and merges the halves.
What is the base case for merge sort's recursive calls?
When the array has only one element, it is already sorted.
What is the role of the `merge()` function in merge sort?
To combine two sorted arrays into a single sorted array.
What are the trade-offs between recursion and iteration?
Recursion can lead to more concise code but may be slower due to function call overhead. Iteration is often faster but can result in more verbose code.
What is the purpose of the index parameter in the recursive array traversal example?
It keeps track of the current position within the array being processed.
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.