Rekursion bedeutet, daß eine Routine eine kleinen Teil eines Problem selbst löst, das Problem dann in kleinere Stücke unterteilt und sich selbst aufruft, um nun eines dieser kleineren Stücke zu bearbeiten. Rekursion kommt üblicherweise dann ins Spiel, wenn sich ein kleiner Teil des Problems leicht lösen und sich das Gesamtproblem einfach in kleinere Teilaufgaben aufteilen läßt.

Das folgende Beispiel soll eine sinnvolle Anwendung der Rekursion zeigen.

Beispiel für den QuickSort-Algorithmus (in Pascal)

Procedure QuickSort
    (
    FirstIndex: integer;
    LastIndex: integer;
    Names: NAME_ARRAY
    );
var 
    MidPoint: integer;
begin
    if ( LastIndex > FirstIndex ) then
        begin
        Partition( FirstIndex, LastIndex, Names, MidPoint );
        QuickSort( FirstIndex, MidPoint - 1, Names );
	QuickSort( MidPoint, LastIndex, Names );
        end;
end; (* QickSort *)