Die Ackermannnfunktion ist eine nach Wilhelm Ackermann benannte, rekursive Funktion.

Sie ist folgendermaßen definiert:

Schreiben wir also eine Funktion mit dem Namen ack und testen danach den Aufruf mit ack(3,4), von dem wir wissen, dass das Ergebnis 125 sein muss.

Die Funktion sieht demnach in etwa so aus:

Würde man den Code so ausführen, erhält man in etwa folgende Ausgabe:

Deep recursion on subroutine "main::ack" at ackermann.pl line 17.
125
Deep recursion on subroutine "main::ack" at ackermann.pl line 21.
Deep recursion on subroutine "main::ack" at ackermann.pl line 21.
Deep recursion on subroutine "main::ack" at ackermann.pl line 21.
Deep recursion on subroutine "main::ack" at ackermann.pl line 21.
Deep recursion on subroutine "main::ack" at ackermann.pl line 21.
Deep recursion on subroutine "main::ack" at ackermann.pl line 21.
Deep recursion on subroutine "main::ack" at ackermann.pl line 21.
...Meldung noch einige Male mehr...
Deep recursion on subroutine "main::ack" at ackermann.pl line 21.
Deep recursion on subroutine "main::ack" at ackermann.pl line 21.
Deep recursion on subroutine "main::ack" at ackermann.pl line 21.
Deep recursion on subroutine "main::ack" at ackermann.pl line 21.
Deep recursion on subroutine "main::ack" at ackermann.pl line 21.
Deep recursion on subroutine "main::ack" at ackermann.pl line 21.
Deep recursion on subroutine "main::ack" at ackermann.pl line 21.

Wenn wir die Funktion nun nicht nur mit 3 und 4 aufrufen würden, sondern mit entsprechend höheren Werten, entstehen wesentlich mehr Fehlermeldungen.

Diese Fehlermeldungen tauchen nur bei der Verwendung von use warnings; auf.

Doch das Weglassen dieser 2 Wörter ist keine akzeptable Lösung.

Eine Lösung wäre, dass wir global die Warnungen für 'recursion's ausmachen. Doch besser ist es in einem naked Block innerhalb der betroffenen Funktion selbst.

Das Ganze sieht dann in etwa so aus:

Ruft man die Funktion nun mit ein wenig erhöhten Parametern auf, merkt man schnell, dass die Geschwindigkeit stark abnimmt. Das Zauberwort um dies ein wenig zu minimieren ist Caching.

Die Idee die dahinter steckt ist folgende:

Bereits berechnete Werte kennen wir bereits, brauchen sie also nicht noch einmal berechnen.

Wir optimieren unseren oberen Code nun dahingehend, dass wir einen Cache einbauen der uns bereits berechnete Werte zurückliefert. Das Ganze sieht dann beispielsweise so aus:

Die Funktion ist nun um einiges schneller.

Die Ackermannfunktion ist ein Beispiel für eine nicht primitiv-rekursive aber berechenbare Funktion. Durch den letzten Aufruf

return ack( $m - 1, ack( $m, $n - 1 ) );

und die tiefe Verschachtelung der Funktionsaufrufe, kommt es leicht zu einem Stapelüberlauf (engl. Stack Overflow), also dazu, dass dem System der Speicher ausgeht.

Das können wir zum Beispiel mit dem Aufruf print ack( 4, 2 ); erreichen.

Nach 20-30 Sekunden kommt folgende Ausgabe:

Out of memory!

Das richtige Ergebnis von ack( 4, 2 ); ist übrigends 2.00352993040684646497907235156025575044782547 x 1019728

Beziehungsweise 10104.295089702969369.

Quelle

Copyright © Tomatenstau.de 2016