Recursion

See recursion.

Recursive methods are those that call themselves. A recursive method should have a base case and recursive case. For example, the factorial function has recursive case $f(n) = n \times f(n-1)$ and base case $f(0) = 1$.

Binary search is a recursive divide and conquer search algorithm for sorted data. It chooses a pivot and recursively searches the half of the list based on the difference between the search term and pivot. Binary search has complexity $O(\log n)$. Binary search is an example of linear recursion, where each recursive call makes only one recursive call.

The Fibonacci function, $F(n) = F(n-1) + F(n-2)$ uses binary recursion, as each call makes two recursive calls. A function making more than two recursive calls is said to use multiple recursion.