Recursion

Question 1

What is a recursive algorithm?

Answer 1

A method that calls itself somewhere inside it’s body of code

Question 2

What is the Recursive case in a recursive algorithm?

Answer 2

Recursively calls the method with different parameters each time, eventually converging on a base case

Question 3

What is a Base case in a recursive algorithm?

Answer 3

Detects a condition or if statement, upon which it provides a final answer

Question 4

What is an example of a recursive data structure?
Explain how it can be recursive, and state the base case and recursive case

Answer 4

A linked list

• When adding to the front of the list, the previous front will become the start of the rest of the list
• The Base case would be an empty list
• The Recursive case includes one item, and then the rest of the list

Question 5

A Binary search is a recursive algorithm. What are the base and recursive case(s) of a Binary search?

Answer 5

• Base case: item not found if the list is too small
• Base case: item found if the middle item is the search term

-Recursive case: Calls the Binary search method using either the left or right half of the list, excluding the middle item