Eine Funktion f(x, y) ist definiert als „ist y gleich 0, gib x zurück; andernfalls gib f(y, x mod y) zurück“. Welchen Rückgabewert liefert der Aufruf f(84, 36), und wie oft wird f aufgerufen, den ersten Aufruf eingeschlossen?

Antwort: A. Rückgabewert 12, 3 Aufrufe

f(84, 36) ruft f(36, 12) auf, weil 84 mod 36 = 12; dieser Aufruf ruft f(12, 0) auf, weil 36 mod 12 = 0; und da y gleich 0 ist, wird 12 zurückgegeben. Die Aufrufe sind f(84, 36), f(36, 12) und f(12, 0), insgesamt drei; es handelt sich um den euklidischen Algorithmus für den größten gemeinsamen Teiler. Da die Funktion das Ergebnis ihres rekursiven Aufrufs direkt zurückgibt (Endrekursion), kann ein Compiler mit Tail-Call-Optimierung sie in eine Schleife umwandeln, sodass sie keinen weiteren Stack-Speicher belegt, wie tief die Rekursion auch wird.