Recursive algorithms are very common in functional programming. In fact, many of our imperative loops can be rewritten as recursive algorithms using pure functions.
However, recursion is not very popular in imperative programming because it has a few issues. First, developers tend to have less practice with recursive algorithms compared to imperative loops. Second, the dreaded stack overflow—recursive calls are placed to the stack by default and if there are too many iterations, the stack overflows with an ugly error.
Fortunately, compilers are smart and can fix this problem for us, while at the same time optimizing recursive functions. Enter tail recursion optimization.
Let's take a look at a simple recursive function. We'll reuse the factorial from the previous section, as follows:
function<int(int)> fact = [&fact](int...