# 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

# What does FibonacciNumber(2) return? What does FibonacciNumber(4) return? 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