Rekursion ermöglicht es, Algorithmen für viele Probleme besonders kurz und elegant zu formulieren, indem der Algorithmus, angewendet auf reduzierte Problemversionen, sich wieder selbst verwendet. Abschnitt 6.1 führt das Prinzip der Rekursion anhand eines weiteren Algorithmus zum Sortieren einer Folge von Zahlen, dem Sortieren durch Mischen, ein. Abschnitt 6.1.2 zeigt, wie dieser Algorithmus als Java-Programm unter Verwendung von Funktionen realisiert werden kann. Dem Sortieren durch Mischen liegt das allgemeine Prinzip des „Divide and Conquer“ zugrunde, das in Abschnitt 6.2 vorgestellt wird. Algorithmen, die diesem Prinzip folgen, lassen sich häufig in natürlicher Weise rekursiv formulieren.