{"id":1932,"date":"2013-06-17T13:53:23","date_gmt":"2013-06-17T11:53:23","guid":{"rendered":"http:\/\/www.tutego.de\/blog\/javainsel\/?p=1932"},"modified":"2016-02-13T09:32:08","modified_gmt":"2016-02-13T07:32:08","slug":"die-java-8-jvm-wird-keine-tail-call-recursion-optimierung-bekommen","status":"publish","type":"post","link":"https:\/\/www.tutego.de\/blog\/javainsel\/2013\/06\/die-java-8-jvm-wird-keine-tail-call-recursion-optimierung-bekommen\/","title":{"rendered":"Die Java 8 JVM wird keine Tail Call Recursion Optimierung bekommen"},"content":{"rendered":"

Endrekursion<\/strong> (engl. Tail Call Recursion<\/strong>) ist eine Besonderheit bei Methoden, dass sie mit einem rekursiven Aufruf enden. Zum Einstieg: Ist die bekannte rekursive Implementierung der Fakult\u00e4t endrekursiv?<\/p>\n

int factorial(int n) {\r\n  if ( n == 0 ) return 1;\r\n  return n * factorial( n \u2013 1 );\r\n}<\/pre>\n
Zwar sieht es optisch so aus, als ob die factorial(int) mit einem Methodenaufruf an factorial(\u2026) endet, doch findet hier keine Endrekursion statt, da nach dem Methodenaufruf noch eine Multiplikation stattfindet \u2013 etwas umgeschrieben ist es besser zu erkennen:<\/p>\n
int factorial(int n) {\r\n  if ( n == 0 ) return 1;\r\n  int fac = factorial( n \u2013 1 );\r\n  return n * fac;\r\n}<\/pre>\n
Die Berechnung der Fakult\u00e4t l\u00e4sst sich umschreiben, so dass tats\u00e4chlich eine Endrekursion sattfindet, und zwar durch Einf\u00fchrung eines Containers f\u00fcr Zwischenergebnisse, genannt Akkumulator:<\/p>\n
int factorial( int n )\r\n{\r\n  return factorialTailrec( n, 1 );\r\n}\r\n\r\nprivate int factorialTailrec( int n, int accumulator )\r\n{\r\n  if (n == 0) return accumulator;\r\n  return factorialTailrec( n \u2013 1, n * accumulator );\r\n}<\/code><\/pre>\n
Die umgeschriebene Version b\u00fc\u00dft gegen\u00fcber der urspr\u00fcnglichen Version an Sch\u00f6nheit ein. Doch endrekursive Aufrufe sind attraktiv, da eine schlaue \u00dcbersetzungseinheit sie so optimieren kann, dass der rekursive Methodenaufruf durch einen Sprung ersetzt wird. In der Java Sprache haben wir keine direkten Spr\u00fcnge, doch im Bytecode schon, sodass die Basis der Optimierung im Grunde so aussehen kann:<\/p>\n
private int factorialTailrec( int n, int accumulator ) {\r\n<\/span><\/pre>\n
start:<\/pre>\n
\u00a0 if ( n == 0 ) return accumulator;<\/span><\/pre>\n
\u00a0 accumulator *= n;<\/pre>\n
\u00a0 n--;<\/pre>\n
\u00a0 goto start;<\/pre>\n
}<\/pre>\n
Die Rekursion ist durch eine ordin\u00e4re Schleife ersetzt, was Stack einspart und eine sehr gute Performance ergibt.<\/span><\/code><\/p>\n
In funktionalen Programmen ergeben sich eher Situationen, in denen Endrekursion vorkommt, sodass es attraktiv ist, diese zu optimieren. Die Standard-JVM kann das bisher nicht, weil Java traditionell keine funktionale Programmiersprache ist, und Endrekursion eher selten vorkommt. Zwar wird die Optimierung von Endrekursion (engl. tail call optimization) immer wieder diskutiert und auch schon in <\/span><\/code>Prototypen ausprobiert, aber nie\u00a0 von der Oracle JVM implementiert. <\/span><\/code>F\u00fcr Entwickler hei\u00dft dass, rekursive Aufrufe nicht umzuschreiben in endrekursive Varianten, da sie sowieso nicht optimiert werden und nur unleserlicher w\u00fcrden, und bei gro\u00dfen Datenvolumen, sprich Stack-Tiefe, auf die \u00fcbliche nicht-rekursive iterative Version umzustellen. Im Fall von factorialTailrec(..) kann dies n\u00e4mlich auch vom Entwickler gemacht werden und sieht so aus:<\/span><\/code><\/p>\n
private int factorialTailrec( int n, int accumulator ) {<\/p>\n
while (n != 0) {<\/span><\/p>\n
accumulator *= n;<\/p>\n
n–;<\/p>\n
}<\/p>\n
return accumulator;<\/p>\n
}<\/p>\n
\u00a0<\/span><\/code><\/p>\n","protected":false},"excerpt":{"rendered":"
Endrekursion (engl. Tail Call Recursion) ist eine Besonderheit bei Methoden, dass sie mit einem rekursiven Aufruf enden. Zum Einstieg: Ist die bekannte rekursive Implementierung der Fakult\u00e4t endrekursiv? int factorial(int n) { if ( n == 0 ) return 1; return n * factorial( n \u2013 1 ); } Zwar sieht es optisch so aus, als […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":"","_links_to":"","_links_to_target":""},"categories":[66],"tags":[],"class_list":["post-1932","post","type-post","status-publish","format-standard","hentry","category-java-8"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/1932","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/comments?post=1932"}],"version-history":[{"count":2,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/1932\/revisions"}],"predecessor-version":[{"id":3287,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/1932\/revisions\/3287"}],"wp:attachment":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/media?parent=1932"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/categories?post=1932"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/tags?post=1932"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}