2.9 Recursive algorithms

Fibonacci numbers

The Fibonacci sequence is a numerical sequence where each term is the sum of the previous 2 terms in the sequence, except the first 2 terms, which are 0 and 1. A recursive function can be used to calculate a Fibonacci number: A term in the Fibonacci sequence.

FibonacciNumber recursive function

Activity 1: FibonacciNumber recursive function.

  1. What does FibonacciNumber(2) return?
  2. What does FibonacciNumber(4) return?
  3. What does FibonacciNumber(8) return?

Recursive binary search

Binary search is an algorithm that searches a sorted list for a key by first comparing the key to the middle element in the list and recursively searching half of the remaining list so long as the key is not found.

Binary search first checks the middle element of the list. If the search key is found, the algorithm returns the index. If the search key is not found, the algorithm recursively searches the remaining left sublist (if the search key was less than the middle element) or the remaining right sublist (if the search key was greater than the middle element).

BinarySearch recursive algorithm

Activity 2: Recursive binary search.

Suppose BinarySearch(numbers, 0, 7, 42) is used to search the list (14, 26, 42, 59, 71, 88, 92) for key 42.

  1. What is the first middle element that is compared against 42?

  2. What will the low and high argument values be for the first recursive call?
    low = 0 high = 2
    low = 0 high = 3
    low = 4 high = 7

  3. How many calls to BinarySearch will be made by the time 42 is found?