none
Erklärung zu endrecursive

    Frage

  • Hallo zusammen,

    ich habe mir ein Thema aufgeschnappt, das ich wohl während meines Studiums verpennt haben muss. Ich programmiere sehr gerne mit Rekursionen. Nun habe ich in den tiefen des Webs den Begriff "Endrekursiv" aufgeschnappt, mit dem eine Rekursion deutlich optimierbar sein soll.

    Ich habe nun sowohl bei Wikipedia als auch bei heise.de folgendes Beispiel aufgeschnappt:

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    
    namespace Endrekursiv {
       public class Program {
          static void Main(string[] args) {
             Console.WriteLine(Recursive(6, 0));
             Console.WriteLine();
             Console.WriteLine(Endrecursive(0, 6));
          }
    
          private static long Recursive(int number, int recurstionDeepness) {
             if(number == 0) {
                Console.WriteLine(new string('\t', recurstionDeepness) + number + " + Recursive(" + number + ", " + recurstionDeepness + 1 + ')');
                return 0;
             }
             Console.WriteLine(new string('\t', recurstionDeepness) + number + " + Recursive(" + number + ", " + recurstionDeepness + 1 + ')');
             long result = Recursive(number - 1, recurstionDeepness + 1);
             Console.WriteLine(new string('\t', recurstionDeepness) + number + " + " + result);
             return number + result;
          }
    
          private static int Endrecursive(int n, int number, int recursionDeepnes = 0) {
             if(number == 0) {
                Console.WriteLine(new string('\t', recursionDeepnes) + number + " + Endrecursive(" + n + ", " + number/* + (recursionDeppnes + 1)*/+ ')');
                return n;
             }
             Console.WriteLine(new string('\t', recursionDeepnes) + number + " + Endrecursive(" + n + ", " + number/* + (recursionDeppnes + 1)*/+ ')');
             int result = Endrecursive(n + number, number - 1, recursionDeepnes + 1);
             Console.WriteLine(new string('\t', recursionDeepnes) + result);
             return result;
          }
       }
    }

    Lt. den Erklärung in den oben genannten Quellen, sollte die Endrekursive Variante Funktionsaufrufe, und damit die Erweiterung des Stacks sparen. Leider konnte ich mir das bisher nicht begreiflich machen, da Konsolenausgabe beinahe identisch ist.

    Folgendes ist die Ausgabe:

    Evtl. ist auch nur meine Ausgabe falsch, oder die Opimierung ist mittels einer Ausgabe nicht erkennbar (wiederverwendung des gleichen Stackframes)?

    Vielen Dank für Eure Erklärungen... :-)


    Viele Grüße Holger M. Rößler

    Mittwoch, 29. August 2012 20:45

Antworten

  • Hallo Holger,

    mir ist es jetzt zu spät um die Links zu suchen, die Du aufgeschnappt hast.
    Aber ich vermute, Du meinst tail recursion.

    Sprachen, die sehr stark auf rekursiven Aufrufen aufbauen, wie der Klassiker LISP -
    wo ich es mal aufgeschnappt habe - kennen dafür Optimierungen, siehe
    Which languages support tail recursion optimization?

    (zumindest wenn die Compiler-Entwickler sich die Zeit dafür genommen haben)

    Dabei wird als Optimierung genutzt, dass das Ergebnis des Funktionsaufrufs
    auf dem Stack liegt und gleich weiter genutzt werden kann - siehe auch das
    Phyton Beispiel auf Stackoverflow.

    C# / .NET kennt das nicht durchgängig nur der 64-Bit-Jitter soll es können,
    siehe Why doesn't .NET/C# optimize for tail-call recursion?
    Sehen kannst Du vermutlich nur, wenn Du im Release-Modus mit Optimierungen arbeitest,
    beim Debug-Modus wird sich das der Jitter "verkneifen".

    Und "Rekursionsliebhaber" sollten bedenken: Is recursion ever faster than looping?
    weswegen es eben ohne solche Optimierungen oft nicht der bessere Weg ist.

    Gruß Elmar

    Mittwoch, 29. August 2012 22:02

Alle Antworten

  • Hallo Holger,

    mir ist es jetzt zu spät um die Links zu suchen, die Du aufgeschnappt hast.
    Aber ich vermute, Du meinst tail recursion.

    Sprachen, die sehr stark auf rekursiven Aufrufen aufbauen, wie der Klassiker LISP -
    wo ich es mal aufgeschnappt habe - kennen dafür Optimierungen, siehe
    Which languages support tail recursion optimization?

    (zumindest wenn die Compiler-Entwickler sich die Zeit dafür genommen haben)

    Dabei wird als Optimierung genutzt, dass das Ergebnis des Funktionsaufrufs
    auf dem Stack liegt und gleich weiter genutzt werden kann - siehe auch das
    Phyton Beispiel auf Stackoverflow.

    C# / .NET kennt das nicht durchgängig nur der 64-Bit-Jitter soll es können,
    siehe Why doesn't .NET/C# optimize for tail-call recursion?
    Sehen kannst Du vermutlich nur, wenn Du im Release-Modus mit Optimierungen arbeitest,
    beim Debug-Modus wird sich das der Jitter "verkneifen".

    Und "Rekursionsliebhaber" sollten bedenken: Is recursion ever faster than looping?
    weswegen es eben ohne solche Optimierungen oft nicht der bessere Weg ist.

    Gruß Elmar

    Mittwoch, 29. August 2012 22:02
  • Hallo Elmar,

    vielen Dank für deine Antwort zu so früher Stunde ;-)

    Ja genau, tail recursion ist das Stichwort.

    Ich habe eine Tutorial für F# durchgearbeitet, dadurch bin ich darauf gestoßen. Da habe ich mich gefragt, ob ich damit meinen bestehenen, rekursiven Code (C# und unmanaged C++) nicht etwas beschleunigen könnte.

    Ich habe nun einige Test gemacht und die Rekursionen mehrfach laufen lassen (100 als Parameter, C#, .net 4.0, ohne Konsolenausgaben):

    Rekursiv (Debug, x64): 0,00125 Sekunden
    Endrekursiv (Debug, x64): 0,0 Sekunden

    Erstaunlicherweise ändern sich die Werte nicht mit den Optimierungen im Releasemode:

    Rekursiv (Release, x64): 0,00125 Sekunden
    Endrekursiv (Release, x64): 0,0 Sekunden

    Somit scheint eine Endrekursive Lösung durchaus was zu bringen. Und je größer der Parameter wird, umso größer wird der Unterschied...

    Der Illusion, dass Rekursionen schneller als Schleifen sind, habe ich mich nie hingegeben. Der Overhead ist einfach deutlich größer. Aber Rekursionen sind in der Regel kürzer, prägnanter, lesbarer...einfach eleganter als diverse "Schleifenorgien".


    Viele Grüße Holger M. Rößler



    Mittwoch, 29. August 2012 23:09
  • Hallo Holger,

    ich habe nun die Lektüre in der Wikipedia und bei Heise nachgeholt.

    Erstere hat wohl ein Informatiklehrer/-dozent geschrieben und mir kam wieder der Satz hoch: "Kein Wunder, dass Informatiker erst programmieren lernen müssen" ;-)
    Da muss man einfach zu lange bohren, bis man zum Kern kommt.

    Zum anderen sage ich nur so viel, dass mich die Tiefe und Akkuratesse der Artikel des Autors an anderer Stelle nicht gerade beeindruckt haben.

    Um die Kirche ins Dorf zurück zu holen:
    Tail Recursion ist wichtig für funktionale Sprachen (wie Lisp, Scheme und F#), die aufgrund ihres Konzepts ansonsten oft ein vorzeitiges Ende beim Stapelüberlauf finden würden. Für Sprachen wie C# nicht so sehr von Bedeutung, da Rekursion eher ein Spezialfall ist - einzig im funktionalen Teil (=> LINQ) kann es Vorteile bringen, da dort (lange) Methodenkette verarbeitet werden müssen (und Daten auf dem Stack übergeben werden.

    Was Deine Messung angeht, dürfte das bei 100 kaum messbar sein und die Unterschiede aus anderen Faktoren kommen - ich hole das nicht nach (ist mir jetzt zu akademisch).

    Als einfacher Test, ob eine Tail Recursion verwendet wird:
    Erhöhe den Wert solange bis eine StackOverflowException bei "Normalrekursion" stattfindet, bei Tail Recursion sollte die wiederum nicht eintreten. Der komplizierte Weg wäre, sich den gejitteten Code anzuschauen, zum Vergleich:
    http://stackoverflow.com/questions/490324/how-do-i-check-if-gcc-is-performing-tail-recursion-optimization oder aber einen StackFrame abrufen (letzteres müsste ich erst probieren, ob es zum richtigen Ergebnis führt).

    Gruß Elmar

    Donnerstag, 30. August 2012 08:04
  • Hi Holger,

    interessant kannte ich auch noch nicht.

    Mir sind mir aufgefallen. Einmal benutzt du long und einmal int.

    In wieweit, dass das Laufzeit beeinflusst, kann ich nicht sagen, ich wurde aber bei Performance vergleiche den gleichen Datentyp nehmen um hier Unterschiede auszuschließen.

    Die Ausgabe z.B "2 + Endrecusive(18,2)" ist denke ich ein wenig verwirrend  es müsste ja nur "Endrecusive(18,2)" heisen.

    Probiere mal beim beiden die Recusion beim Return zu verwenden und schau dir den Speicherbedarf an.

     private static long Recursive(int number, int recurstionDeepness) {
             if(number == 0) {
          
                return 0;
             }
                return number + Recursive(number - 1, recurstionDeepness + 1); ;
          }
    
          private static long Endrecursive(int n, int number, int recursionDeepnes ) {
             if(number == 0) {
                return n;
             }
                return Endrecursive(n + number, number - 1, recursionDeepnes + 1); ;
          }

    Was die Lesbarkeit angeht, wenn man das Prinzip der Recusion kennt hast du sicher recht.

    Wenn nicht ist eine Schleife einfacher verständlich.

    Und was die Preformanc angeht.

    Ich hatte es mal am Beispiel der Fibonacci Zahl ausprobiere und war wirklich überrascht wie viel Schneller die Schleife war.

    MFG

    Björn

     

    Donnerstag, 30. August 2012 09:02
  • Hallo,

    ich habe nun herausgefunden dass der C# Compiler als auch die .net Runtime sehr wohl dieses Opitmierung kennen und auch nutzen. Und das sowohl für 64- als auch 32-Bit.  (x64 und x86).

    Ich habe mich mal etwas in die Materie eingelesen und bin dabei auf Basics gestoßen, die ich im ersten Beispiel falsch gemacht habe.

    So kann der Compiler die Optimierung natürlich nur durchführen, wenn nach dem Rekursionsaufruf, die Methode nichts mehr tut. Ansonsten muss sich das Programm (logischerweise) die Rücksprungadresse merken, um den noch darin enthaltenen Code noch auszuführen. Und somit kann auch der aktuelle StackFrame nicht wiedeverwendet werden, sondern es muss ein neuer Aufgebaut werden.

    Hier ein Beispiel, bei dem die Endrekursion "unendlich" tief sein kann :)

    using System;
    using System.Numerics;
    
    namespace Endrekursiv {
    	public class Program {
    		static void Main(string[] args) {
    			BigInteger result = 0;
    			TimeSpan startTime = DateTime.Now.TimeOfDay;
    			result = Recursive(16778);//Maxmial mögl. Zahl, sonst StackOverflow
    			Console.WriteLine(DateTime.Now.TimeOfDay - startTime);
    			Console.WriteLine(result);
    
    			Console.WriteLine();
    
    			BigInteger endRecursiveResult = 0;
    			startTime = DateTime.Now.TimeOfDay;
    			Endrecursive(65536*128, ref endRecursiveResult); //Zahl kann hier beliebig groß gewählt werden :D
    			Console.WriteLine(DateTime.Now.TimeOfDay - startTime);
    			Console.WriteLine(endRecursiveResult);
    		}
    
    		private static BigInteger Recursive(BigInteger number) {
    			if (number == 0) {
    				return 0;
    			}
    			return number + Recursive(number - 1);
    		}
    
    		private static void Endrecursive(BigInteger number, ref BigInteger result) {
    			if (number == 0) {
    				return;
    			}
    			result = number + result;
    			Endrecursive(number - 1, ref result);
    		}
    	}
    }

    Viele Grüße Holger M. Rößler

    Sonntag, 2. September 2012 16:15