=> Wenn man den richtigen Algorithmus wählt, ist die Frage rekursiv/iterativ untergeordnet, solange man es vernüftig macht.
Die Wahl des „richtigen“ (was ist damit konkret gemeint?) Algorithmus besteht doch oft genug in der Entscheidung, ob rekursiv oder iterativ.
Ich schlage mal folgendes vor: Vergleiche mal die Berechnung der Koeffizienten eines charakteristischen Polynoms einer quadratischen Matrix mit Rekursion (nach der Determinantenberechnung nach dem Laplaceschen Entwicklungssatz) mit ihren iterativen Pendants (der schnellste mir bekannte ist der von Le Verrier). Die Komplexität unterscheidet sich zwischen beiden um astronomischen Größenordnungen!
All' die, dier hier der Rekursion das Wort reden, konnte ich, sofern beide Alternativen (als Rekursion und Iteration oder sogar simpleres) zur Lösung eines Problemes verfügbar sind, noch keine einzigen Fall nennen hören, bei dem die Rekursion hinsichtlich Komplexität die überlegene Lösung darstellt. Ich bin gespannt darauf.