RecursionBinarySearch

Question 1

What is a recursive function?

Answer 1

A fn that calls itself.

Question 2

What is the base case in recursion?

Answer 2

The base case is the part of the function
that determines when to stop and does not
make a recursive call.

Question 3

What is the typical recursive pattern?

Answer 3

void factorial(int n) {
if(n < 0) {
return -1;
} else if(n == 0 || n == 1) {
return 1;
} else {
int rest = n - 1;
int factRest = factorial(rest);
return n * factRest;
}
}

Question 4

How does binary search work?

Answer 4

Begin with a start index of 0 and an end index
of length-1.
○ Examine the value at the mid point (half way
between the start and the end).
■ If the mid value is the target, return true.
■ If the mid value is larger than the target,
set end to mid - 1.
■ If the mid value is less than the target,
set start to mid + 1.
○ Repeat until the target is found, or start >
end.