Java Recursion: Tracing and Algorithms Free Online FlashCards

What is recursion?

Recursion is a problem-solving technique in which a method calls itself to solve a smaller version of the same problem.

What two cases must a recursive method normally contain?

A base case stops further recursive calls; a recursive case calls the same method on a smaller or simpler problem.

Why must each recursive call make progress?

The recursive case must move the argument or range closer to the base case. Otherwise, the method may never terminate and can cause a StackOverflowError.

What does factorial(4) return if factorial(0) returns 1?

24. The calls reduce as factorial(4) = 4 × factorial(3) = 4 × 3 × 2 × 1 × factorial(0), and factorial(0) returns 1.

How does the call stack handle recursive calls?

Each recursive call creates a new stack frame with its own parameters and local variables. Calls descend toward the base case, then suspended calls finish as returns move upward.

What does printUp(3) print?

It prints 1 2 3. Because printing occurs after the recursive call, the output happens while the calls return.

What does countChar("banana", 'a') return?

3. The method examines the first character, adds 1 when it matches 'a', and recursively processes the remaining substring until it reaches the empty string.

What does arraySum({4, 7, 2}, 0) return?

13. arraySum adds values[0], values[1], and values[2], then reaches the base case when index equals values.length.

Where does binary search find 25 in {3, 8, 12, 17, 25, 31, 40}?

4. Binary search checks indices 3, 5, and then 4; values[4] is 25.

What is the main structure of merge sort?

Merge sort recursively sorts the left and right halves, then merges those sorted halves. Its base case is a portion with zero or one element.

What does reverse("cat") return?

"tac". reverse removes the first character, reverses the remainder, and appends the removed character at the end.

What does isPalindrome("racecar") return?

true. The method compares matching outer characters, then recursively checks the smaller middle substring until reaching a string of length one.