The Complete Rust Programming Reference Guide

Recursion

Since all recursive algorithms can be unrolled into a loop, they can achieve the same results. However, recursion, or more specifically backtracking (which will be discussed in more detail in Chapter 21, Random and Combinatorial), makes it easier to create higher runtime complexities.

Typical combinatorial problems result in exponential runtimes, since there are a number of variations (such as different colors) that have to be enumerated n times so that a constraint is satisfied, which is only evaluated at the end. If there are two colors, the runtime complexity will therefore be O(2ⁿ) for a sequence of n colors, if no two colors can be adjacent to each other in a graph (graph coloring problem).

Recursive algorithms also make it ...