TailRecursion ist unter anderem die Basis für eine PerformanceOptimierung an sich eher langsamer rekursiver Algorithmen.

Eine Folge von rekursiven Funktionsaufrufen (z.B. einer rekursiven Fakultätsberechnung) baut ja eben so viele Functions-Call-Frames auf und auch wieder ab. D. h. der Platz für automatische Variablen (in C-Terminologie) wird belegt und im Function-Call wird die Return-Adresse deponiert bzw. verwendet. TailRecursion vermeidet diesen Resourcenaufwand im Zusammenspiel zwischen einem optimierenden Compiler und einem kundigen Programierer und ersetzt den Aufruf gedanklich durch ein simples "goto" zum Anfang der Funktion. Es ist naheliegend, dass dies praktisch die Performance einer schleifenorientierten Lösung des Problems bringt, unter Erhalt einer rekursiven Formulierung der Implementierung. Allerdings ist die tail-rekursive Variante oft deutlich unintuitiver und umständlicher sowohl als die einfache Rekursion, als auch als die iterative Formulierung. Man sollte also einen konkreten Grund haben, sie zu verwenden.

Wenn also aus einer normalen Fakultätsberechnung:

int fact(int n) { int i; int result = 1; for (i = 1; i <= n; i++) { result *= i; } return result; }

im Zuge einer rekursiven Formulierung ein schönes, aber ineffizientes, rekursives

int fact(int n) { if (n <= 1) { return 1; } return n*fact(n-1); }

wird, dann kann durch eine Formulierung, die TailRecursion zulässt:

int fact_tail(int n, int produkt) { if (n <= 1) { return produkt; } return fact_tail(n-1, n*produkt) } int fact(n) { return fact_tail(n, 1); }

de facto einem entsprechend optimierenden Compiler folgendes ermöglicht werden:

int fact_tail(int n, int produkt) { begin: if (n <= 1) { return produkt; } produkt = n*produkt; n = n-1; goto begin; } int fact(n) { return fact_tail(n, 1); }

was in der nachfolgenden Optimierung vermutlich exakt das gleiche Ergebnis wie die ursprüngliche Schleifenkonstruktion erzeugt.

Weil rekursive Konzepte typischerweise am Beispiel der Fakultätsberechnung demonstriert werden, und das Beispiel einfach und leicht nachvollziehbar ist, wird es hier auch verwendet, ohne dass dabei behauptet wird, das Beispiel sei geeignet, die Vorteile der veranschaulichten Konstruktionen zu demonstrieren.

Anmerkung: In C++ lässt sich die tail-rekursive Variante aber auch noch etwas eleganter darstellen:

int fact(int n, int produkt=1) { if (n <= 1) { return produkt; } return fact(n-1, n*produkt); }

- diese kann man ganz normal mit "fact(n)", wo n eine (int) Zahl ist, aufrufen.