There are also some algorithms which naturally have two phases, such as minimax (min and max), and these can be implemented by having each phase in a separate function with mutual recursion, though they can also be combined into a single function with direct recursion.
In mathematics, the Hofstadter Female and Male sequences are an example of a pair of integer sequences defined in a mutually recursive manner.