Webo - Sa 05.02.11 13:38
Titel: Rekursionsarten

---

Hallo,

ich wiederhole grade unser Infoskript und beim Thema Rekursion bleib ich hängen :roll:
Wir hatten verschiedene Arten von Rekursion besprochen:

• Lineare Rekursion
  
• Primitive Rekursion
  
• Endrekursion
  
• nichtlineare, baumartige Rekursion
  

Wenn ich mir so die einzelnen Definitionen der Arten durchlesen, verstehe ich das halbwegs. Es hapert aber daran, dass dann auch wirklich zu erkennen an einem Beispiel. Ok, bei der baumartigen Rekursion bekomm ich auch das hin, aber die drei anderen bereiten mir noch Kopfzerbrechen.
Vielleicht könnte mir jemand ganz einfach Beispiele (als Code) zu den drei ersten Typen liefern.
Dann habe ich noch ein Beispiel aus der Probeklausur. Wenn Ihr mir da begründen könntet, um welche Art von Rekursion es sich handelt, wäre ich sehr dankbar.



Mit freundlichen Grüßen

Webo


Moderiert von Kha: Topic aus Sonstiges (Delphi) verschoben am Sa 05.02.2011 um 13:23

Kha - Sa 05.02.11 14:32

---

Die Standardantwort bei Hausaufgabenthreads ;) : Welche Gedanken hast du dir denn schon selbst zu dem Code gemacht?
Bedenke vor allem, dass sich die vier Fälle nicht unbedingt gegenseitig ausschließen :) ...

elundril - Sa 05.02.11 14:38

---

Zusätzlich gib es zu jedem dieser Punkte einen wunderbar schönen und langen Wikipediaartikel, so nebenbei erwähnt. ;)

lg elundril

Webo - Sa 05.02.11 15:01

---

Gedanken habe ich mir da schon viele zugemacht:

So, wie ich das gedacht habe kann das Beispiel eine:
- lineare Rekursion sein, da pro Stufe genau ein rekursiver Aufruf erfolgen kann (stehen zwar zwei drin, aber durch if else wird ja nur eines "genommen")
- primitive Rekrsion nicht unbedingt sein, da zwar in x*f1(x, y-1); eine Verschiebung nur um 1 vorliegt, aber auch nur beim y-Parameter und auch nur im else-Konstrukt
- Endrekursion nicht unbedingt sein, da je nach Wert des Parameters ein neuer Rekursionsaufruf oder return 1; behandelt wird.
- baumartige Rekursion nicht sein, da nix baumartiges vorhanden und noch nichtmal eine Ankreuzmöglichkeit dafür in der Klausur ;-)

Somit wäre es für mich eine lineare Rekursion. Sicher bin ich mir da aber nicht. Vondaher bräuchte ich mal Vergleiche zu anderen Funktionen, wo feststeht, was es ist ...

Die Wikipediaartiel habe ich mir angeschaut, aber ich verstehe ehrlich gesagt nur den der Endrekursion.

Kha - Sa 05.02.11 16:57

---

Webo hat folgendes geschrieben :

Gedanken habe ich mir da schon viele zugemacht:

Na das sieht doch schonmal ganz gut aus :) .

Webo hat folgendes geschrieben :

- lineare Rekursion sein, da pro Stufe genau ein rekursiver Aufruf erfolgen kann (stehen zwar zwei drin, aber durch if else wird ja nur eines "genommen")

Ist auf jeden Fall linear, ja. Aber nur höchstens ein Aufruf durch den ersten Fall.

Webo hat folgendes geschrieben :

- primitive Rekrsion nicht unbedingt sein, da zwar in x*f1(x, y-1); eine Verschiebung nur um 1 vorliegt, aber auch nur beim y-Parameter und auch nur im else-Konstrukt

Ist keine primitive Rekursion, stimmt. Dafür müssten alle Aufrufe von der Form f1(x-1, y) bzw. f1(x+1, y) sein.

Webo hat folgendes geschrieben :

- Endrekursion nicht unbedingt sein, da je nach Wert des Parameters ein neuer Rekursionsaufruf oder return 1; behandelt wird.

Ist keine Endrekursion, stimmt. Aber nicht wegen des return 1, sonst könnte eine Endrekursion ja nie halten ;) . Nach Wiki heißt es "Spezialfall der linearen Rekursion, bei der jeder rekursive Aufruf die letzte Aktion ist." und eben nicht "bei der jede letzte Aktion ein rekursiver Aufruf ist." :!:
Das eigentliche Problem ist return x*f1(x, y-1), weil hier nach dem Aufruf noch eine Multiplikation folgt.

Webo hat folgendes geschrieben :

Vondaher bräuchte ich mal Vergleiche zu anderen Funktionen, wo feststeht, was es ist ...

Um bei deinem Beispiel zu bleiben:

• endrekursiv (damit linear rekursiv):
  
  
  C#-Quelltext

  1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:

  int f1(int x, int y) { f1(x, y, 1); } int f1(int x, int y, int acc) {   if (y <= 0 ) return acc;   if (y % 2 ==0)     return f1(x*x, y/2, acc);   else     return f1(x, y-1, x * acc); }

  
  
• primitiv rekursiv (damit linear rekursiv) (anderer Algorithmus):
  
  
  C#-Quelltext

  1: 2: 3: 4: 5: 6: 7:

  int f1(int y, int x) {   if (y <= 0 )     return 1;   else     return x * f1(y-1, x); }

Jetzt darfst du daraus eine Funktion, die primitiv rekursiv und endrekursiv ist, bauen :mrgreen: .

Webo - Sa 05.02.11 17:28

---

Woah, ich bin auf dem Weg es zu begreifen :o
Ja klar, Endrekursion geht nicht, weil die Multiplikation noch davor steht ...

Zitat:

endrekursiv (damit linear rekursiv):

Zitat:

primitiv rekursiv (damit linear rekursiv)

Also beinhaltet eine primitive Rekursion und eine Endrekursion immer die lineare Rekursion ?

Kha - Sa 05.02.11 18:14

---

http://de.wikipedia.org/wiki/Rekursion#Formen_der_Rekursion hat folgendes geschrieben:

Die primitive Rekursion ist ein Spezialfall der linearen Rekursion. [...] Die endständige oder repetitive Rekursion (Tail Recursion oder Endrekursion) bezeichnet den Spezialfall der linearen Rekursion [...]

Wichtig ist, wie meine Beispiele gezeigt haben dürften, dass nicht alle primitiven Rekursionen endrekursiv sind und umgekehrt, Funktionen aber trotzdem beides zugleich sein können. Wer möchte ein Euler-Diagramm zeichnen ;) ?