14. Recursion.md

1. Recursion

Recursion is the ability for a function to call itself directly or indirectly. A recursive function solves a particular problem by calling a copy of itself and solving smaller subproblems of the original problems.

An important aspect of recursion is that we should provide a certain case in order to terminate the recursion process.

Recursion in pseudocode as seen in the binary search pseudocode:

if no doors
    return false
if number behind middle door
    return true
else if number < middle door
    search left half
else if number > middle door
    search right half

We're using the same search algorithm for each half. This seems like a cyclical process that will never end, but we're actually changing the input to the function and dividing the problem in half each time, stopping once there are no doors left.