# Rekursiv!



## yeronimo (24. November 2008)

Ich hab mal eine Frage und vielleicht kann sie mir ja hier besser beantwortet werden.
Was genau ist eine rekursive Methode ?


Soweit ich das bis jetzt herausgefunden habe, ist das eine methode die sich SELBST im body der Methode immer wieder aufruft ?

Oder was genau bedeutet in der Programmierung "Rekursive Methode" ? 

Bitte eine möglichst einfache Erklärung !  


 Besten dank im voraus!


p.s. Weiß nicht ob ich hier richtig gepostet habe, aber in meinem Fall hat es mit Java Methoden zutun und deshalb hoffe ichhier an der richtigen Stelle gelandet zu sein-


----------



## kuhlmaehn (24. November 2008)

Rekursiv bedeutet allgemein, dass eine Funktion etwas berechnet indem sie sich (zum Teil) selber aufruft.
Willst du z.B. die Fakultät einer Zahl berechnen (z.B. fak 4 = 1*2*3*4) kannst du das rekursiv machen. Dazu brauchst du einen Rekursionsanker und einen allgemeinen Teil:

```
fak 1 = 1
fak n = n * fak (n-1)
```
Der Anker ist hier 1...
Jetzt kannst du das mal einfach durchspielen: Setzt du 4 ein, so wird sie bei n eingesetzt. fak 4 ist also 4 * fak (3).
Daraus wird dann: fak 4 = 4 * 3 * fak(2) und daraus: fak 4 = 4 * 3 * 2* fak(1).
fak 1 ist ja als Anker extra definiert und damit hält hier die Rekursion mit:
fak 4 = 4 * 3 * 2 * 1

Das kannst du so dann auch ohne probleme in Java implementieren. Allerdings nicht so schön übersichtlich, sondern eher so:

```
public int fak (int n) {
if (n == 1) {
return 1;
}
else {
return n * fak(n-1);
}
```
Eine "Programmiersprache" die das übersichtlicher handhabt ist z.B. haskell.


----------



## Navy (24. November 2008)

Im Grund hast Du das Prinzip richtig erkannt. Rekursion bedeutet, dass eine Funktion sich immer wieder selber aufruft, bis eine Abbruchbedingung zutrifft und diese Funktion einen Wert/Ergebnis zurückliefert.

Als Beispiel kannst Du Dir die die mathematische Operation der Multiplikation von natürlichen Zahlen vorstellen, die auf einfache Weise durch Addition und Subtraktion dargestellt werden kann.

Iterativ: n * m = m_ + m_(n-1) + ... + m_(1)

Rekursiv über Funktion a:
 a(m,1) = m (die Abbruchbedingung)
 a(m,n) = m + a(m,n-1) (der Rekursionsaufruf)


----------



## MAN (24. November 2008)

(die langsamste nicht wissenschaftliche Antwort ):

Hallo yeronimo,

deine Frage hast du dir genau mit folgendem Zitat beantwortet:



yeronimo hat gesagt.:


> Soweit ich das bis jetzt herausgefunden habe, ist das eine methode die sich SELBST im body der Methode immer wieder aufruft ?





Beispiel:


```
public static void main(String args[]) {
    printNumbers(0);
}

private static void printNumbers(int startNumber) {
    System.out.println(startNumber);

    if(startNumber < 6) {
        printNumbers(startNumber++);
    }
}
```

Ausgabe:

```
0
1
2
3
4
5
```


Viele Grüße,
MAN


----------



## yeronimo (24. November 2008)

danke danke !!  hört sich schon gut an


----------



## yeronimo (24. November 2008)

vielleicht kann mir dann noch einer erklären warum in meiner Methode aufeinmal das funktioniert was ich nicht gedacht hätte.


```
public float power (int x, int n)
    {
        if(n >= 0)
        { 
            if(n!=0)
            {
                return x*power(x,n-1);
                //return x*power(x,n-1);
            }else{
                return 1;
            }
        }else{
            System.out.println("n is a negative number!");
        }
        return 1;
    }
```

das return x*power(x,n-1)

hatte ich ausprobietr ohne damit zu rechnen das es funktioniert. Die Gleichung hatte ich ja bereits- 

Kann mir einer erklären was GENAU Zeile fuer Zeile abläuft wenn sich dieses return aufruft ? 
Ich bin bereits mit dem Debugger durchgegangen, aber hilft mir auch nicht viel weiter.
Meiner Logik nach passiert bei einer 2^3 eingabe fuer x, n das hier: 

x(x(x*1))
2(2(2*1))
= 8 

vorrausgesetzt das ist richtig, erklaert sich fuer mich immernoch nicht was die ganze Zeit mit dem N passiert, denn eigetlich muss er das ja benutzen um zu quadrieren.

Ich meine damit nehmen wir mal an ich habe dieses hier:

falls der Teiler durch den ich teilen möchte 11, also ungerade ist soll er nochmal mit x malnehmen nachdem er "(x^5) *(x^5)" gerechnet hat. Ist n ungerade also 10 soll er das nicht tun.

Meine Idee  hier war eine if abfrage mit modulo die prüft ob ungerade, wenn ja dann das hier: 

return x*power(x,n)*x

wenn nein dann ohne x.  Meine Frage hier wieder WAS wird an der Stelle von "power(x,n) " eingesetzt wenn wir das als Rechnung sehen ? 

ist das dann :

x * (x(x(x...*1) *x ? 

Wenn ja, meine Frage hier wieder was ist mit dem N ?  
Als nächstes Beispiel hätte ich dann : 

Ich möchte eine rekursive FUnktion, diese Funktion soll bei jedem aufruf power(x, n/2) aufrufen. Das ansich ist ja kein Problem, aber ich verstehe nicht was genau da vor sich geht, denn ansich ruft der doch die Funktion jedesmal mit einem anderen N wert auf die er aber gar nicht quadriert ?


Um auf die Buchaufgabe zurueckzukommen: 



> Write an improved recursive version of power(x,n) that works by breaking n down into halves(where half of n=n/2), squaring power(x,n/2), and multiplying by x again if n was odd.
> For example, x^11 = (x^5)*(x^5)*x, whereas x^10 = (x^5) * (x^5). Find a suitable base case to stop the recursion.



Falls mein wirres gequtsche da oben keinen Sinn gemacht hat dann ignoriert das einfach und bitte erklärt mir wie ihr diese Aufgabe interpretieren würdet und erklärt mir wie dieses return x*power(x,n) genau arbeitet(bitte schritt fuer schritt^^). 
Meine bereits geschriebene Power Methode hab ich ganz oben angehängt.


ALLERBESTEN dank


----------



## zerix (25. November 2008)

Hallo,

du sollst in die Methode so gestalten, dass der Wert n statt runtergezählt immer halbiert wird. 

Also angenommen dein n wäre 10, dann soll grob gesagt, deine Methode nicht x^10 rechnen, sondern x^5*x^5. 

x*power(x,n) heißt, dass deine aktuelle Zahl mit dem Ergebnis x^n multipliziert wird. 

Beispiel:
2^3 = 2 * 2^2

Ich versuch das Prinzip der Rekursion mal anhand dieser Aufgabe besser zu erklären. 
Der Lehrer kommt zu dir hin und sagt gib mir mal das Ergebnis von 2^3. Damit du dir nicht zuviel arbeit machst, darft du einen Teil der Aufgabe abgeben. Also bleibt für dich dann die Aufgabe 2 * das Ergebnis von 2^2.  Da fragst du deinen Nachbarn, nach dem Ergebnis von 2^2. Wie er auf das Ergebnis kommt ist egal. Er gibt dir das Ergebnis und so kannst du dein Ergebnis auch ausrechen. 
Dein Nachbar kann es natürlich genauso machen und dessen Nachbar und dessen Nachbar usw.

Also grob gesagt, delegierst du einfach einen Teil der Aufgabe an einen anderen. 

Also: 2^3
power(2,3)
2 * power(2,3-1)
2 * power(2,2)

deine 2 * das Ergebnis von deinem Nachbarn, der 2^2 ausrechnet.


Deine neue Aufgabe sieht jetzt so aus, dass du nicht wie im Beispiel, du deine 2 behälst und du deligiert 2^2, sondern, die Aufgabe müsste jetzt so aussehen

Aufruf: power(2,3);
Jetzt musst du n halbieren. In dem Fall ist n=3.
3/2 = 1 Rest 1

Also würdest du dieses mal Aufgaben an mehrere Nachbarn deligieren.
power(2,3) = power(2,1)                        *  power(2,1)                         * power(2,1)
Aufgabe     = 2^die erste hälfte von n   * 2^die zweite hälfte von n * 2^den Rest 

Da durch 2 geteilt wird, ist der Rest entweder 0 oder 1.

Ich hoffe, das ist so halbwegs verständlich erklärt. 

MFG

Sascha


----------



## yeronimo (25. November 2008)

schonmal viel verständlicher erklärt allebesten dank ! 
Jedoch hab ich noch eine sache. 
Das return x*power(x,n) ist ja an sich einfach gesagt das x mal das ergebnis von power(x,n)
mein Problem hier ist das ja eigentlich von der Methode die ich wieer aufgerufen habe KEIN wirkliches ergebnis zurueckgegeben wird ? sondern eine weitere Aufgabe das x*(powerx,n) und das wird solange gemacht bis halt dann 1 returned wird ? 

also so gesehen sieht fuer mich der programablauf so auf: 

bei einer aufgabe 2^3:
2*(2*(2*1)) 

dabei ist wie ich oben geschrieben hab ja irgendwie fuer andere N's (also im anderen Fall n/2) nicht korrekt....

Für mich fehlt irgendwie das return eines ergebnis in Form einer Zahl.


----------



## zerix (25. November 2008)

Genau, das läuft so lange bis 1 zurück gegeben wird. Denn irgendwann kommt man zu 2^0 und das ist 1. Bei jeder Rekursion braucht man einen solche Abbruchbedingung, da die Rekursion sonst läuft bis der Speicher voll ist. 
Wie gesagt, du musst dir das ganze bildlich vorstellen. Bei dem Beispiel mit deinem Nachbarn, gibst du ihm ja auch nur die Aufgabe 2^2. Dir ist es ja egal, wie er zu dem Ergebnis kommt. 

Hier hab ich mal versucht Rekursion zu erklären. Vielleicht hilft es dir ja.
http://www.tutorials.de/forum/java/278928-rekursion-aber-wie.html


Dein Lösung ist nach der Aufgabenstellung falsch. Ich hab oben erklärt wie es aussehen müsste. 



MFG

Sascha


----------



## tim staeglich (25. November 2008)

Noch ein paar kurze Tipps: 

Parameter (Ergebnis-) Werte rekursiver Methoden werden auf dem Stack abgelegt.
Erfahrungsgemäß haben hier einige am Anfang Verständnisschwierigkeiten.
Der Stack ist Dein Zwischenspeicher.

Dann unterscheidet man lineare und nicht lineare Rekursionen:

Linear wäre eine einfache Rekursion, wie z.B. Fakultäten zu berechnen.
Der Stack speicherte alle Aufrufe bis zur Endbedingung und multipliziert die Werte dann auf. Die Rekursion wird einmal durchlaufen.

Nichtlinear:
Berechnet man Fibonacci Zahlen oder traversiert Bäume, wird die Rekursion mehr als einmal innerhalb der Rekursion durchgeführt.

Z.B. prüfte man innerhalb der Methode, ob der aktuelle Wert eine Collection oder schon ein Blatt ist. Ist es eine Collection mit Blättern, riefe man sie (die Methode) noch einmal auf.
und führe anschließend mit der aktuellen Methode fort.

Grüße Tim


----------



## Oliver Gierke (25. November 2008)

Beliebtes Zitat:


> Um Rekursion zu verstehen, muss man Rekursion verstehen.





Gruß
Ollie


----------



## yeronimo (25. November 2008)

so langsam wird es mir klarer, zwar noch nicht perfekt klar.... aber klarer. Deine Erklärung auf dem Link hat mir das schonmal ein stueck besser erklaert  !
Fuer jde weitere Erklärung bin ich dennoch dankbar ^^


----------

