Chris Weed - Functional Programming with C++

A difficulty with recursive algorithms is a computers stacklimit, which will be violated with too many recursive calls. Modern C++compilers implement tail-call optimization, and properly structuredtail-recursive functions are not limited by the stack size. The compilergenerates code that does not add a stack frame and will not exceed the stacklimit with a high number of recursive calls. This chapter covers recursive implementations of STLalgorithms, and most are implemented with tail-recursion. Some algorithmsinclude non-tail-recursive implementations for exposition or when they arefound to compile to code that will not exceed the stack. All of the functionsin this chapter were tested with a very large recursion depth, and noneresulted in a segmentation fault.

Most of the algorithms covered in this chapter arenon-modifying algorithms that will not modify the data processed by thealgorithm. These algorithms can process data accessed by const iterators that transformthe data without changing it. Iterative implementations of these algorithms areavailable for comparison at the website http://cplusplus.comhere: http://www.cplusplus.com/reference/algorithm/ http://www.cplusplus.com/reference/numeric/