Array nach Wert prüfen rekursiv

[bindankbar]

Hi sagen wir mal ich habe einen COde der so aussieht:

 public static int calculateBinomialCoefficient (int n, int k)
   {
      if (k == 1)
         return n;
      else if (n >= k && k == 0)
         return 1;
      else
       return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
 
   }
}

Nun hat mein Prof gemeint, dass die rekursion nicht linear ist und zu vielen gleichen Aufrufen mit gleichen Parameterkombis führt. EIne Möglichkeit damit das besser läuft ist es berechenete Binomialkoeffizienten in einem zwei dimensionalen Array zu speichern und vor einem rekursiven Aufruf zu prüfen, ob die Lösung bereits 1x exisitert hat. Wenn ja soll ich den Wert vom Array ausgeben, wenn nicht soll ich den Wert im Array speichern. Einen Array haben wir schon gegeben, mit der perfekten Länge. Dann habe ich mir überlegt, dass man das so umschreiben kann:

 public static int calculateBinomialCoefficient (int n, int k)
  {
   if (k == 1)
     return n;
   else if (n >= k && k == 0)
     return 1;
  else{
        for (int a=0; a<array.length;a++)
           {
            for(int b=0; b<array.length;b++)
              {
                if (array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k))
               {
                    return array[a][b];
                }else if(array[a][b]==0)
                {
                    array[a][b]=(n * calculateBinomialCoefficient(n - 1, k - 1) / k);
                    return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
                }
            }
        }
    }

Das ist jetzt keine Hausaufgabe oder so, sondern freiwillig, bei mir ist es so, wenn ich korrekten Code sehe, kann ich nachvollziehen warum etwas wie war und es nächstes Mal richtig. Und ich habe das als Übung versucht noch umzusetzen aber seit paar Stunden keine Ahnung wo der Fehler ist. Wäre cool, wenn das einer vielleicht verbessern kann, damit ich die korrekte logischen Schlüsse zusammenfassen kann und mir merken kann, warum man es so macht und es verstehe.

Sorry das die Tabs beim zweiten bisschen falsch sind, habe das eigentlich versucht korrekt zu machen, aber bin da total dumm online, bei meinem muss ich nur Tab drücken und alles ist richtig eingerückt, das manuell zu machen ist doch komplexer als gedacht.

 

[mihe7]

Nun hat mein Prof gemeint, dass die rekursion nicht linear ist

Dann hast Du ihm aber einen anderen Code gezeigt.

 

[bindankbar]

Dann hast Du ihm aber einen anderen Code gezeigt.

Das ist auch nicht der code von ihm, seinen code dürfen wir nicht posten, aber ist sehr ähnlich, also eigentlich das gleiche nur bisschen anders. ALso hatten da was im ersten Teil vorgegeben, was man noch Ergänzen musste,bei mir kommt auch das richtige Ergebnis, er meint, dass das so so sei, also nicht linear.

 

[mihe7]

Der Punkt ist, dass in einer nicht-linearen Rekursion der Rekursionsaufruf mehrfach ausgeführt werden kann. Daher macht es keinen Sinn, sich darüber anhand dieses Codes (lineare Rekursion, endrekursiv) Gedanken zu machen.

Im Prinzip solltest Du einfach genau(!) das machen, was der Prof. geschrieben hat. Und in der Regel sieht das so aus, dass Du mit dem zweidimensionalen Array natürlich unmittelbar auf die Lösung zugreifen kannst (die Indizes entsprechen Deinen Parametern). Schleifen solltest Du da nicht benötigen.

 

[bindankbar]

Der Punkt ist, dass in einer nicht-linearen Rekursion der Rekursionsaufruf mehrfach ausgeführt werden kann. Daher macht es keinen Sinn, sich darüber anhand dieses Codes (lineare Rekursion, endrekursiv) Gedanken zu machen.

Im Prinzip solltest Du einfach genau(!) das machen, was der Prof. geschrieben hat. Und in der Regel sieht das so aus, dass Du mit dem zweidimensionalen Array natürlich unmittelbar auf die Lösung zugreifen kannst (die Indizes entsprechen Deinen Parametern). Schleifen solltest Du da nicht benötigen.

Also leider keine Ahnung. Aber habs hinbekommen, hat nur bisschen gedauert

 

[mihe7]

Nehmen wir mal die Fibonacci-Folge. Wir wollen den Wert des n-ten Glieds bestimmen:

public int fibonacci(int n) {
    if (n < 1) return 0;
    if (n < 2) return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}

Hier hast Du eine nicht-lineare Rekursion, weil Du fibonacci mehrfach rekursiv aufrufst. Betrachtet man im "Uraufruf" den linken Term fibonacci(n-1), dann wird bei dessen Ausführung im linken Term fibonacci(n-2) aufgerufen. Also genau das, was im Uraufruf dem rechten Term entspricht. Heißt also: hier werden sehr viele Berechnungen wiederholt.

Das lässt sich beschleunigen mit einem Array. Beim rekursiven Abstieg im linken Term werden alle unbekannten Folgeglieder zwischen n-1 und 2 (inkl.) berechnet. Speichert man die Werte in einem Array, kann man den Wert von fibonacci(n-2) unmittelbar aus diesem Array erhalten.

public int fibonacci(int n) {
    values = new int[n+1];
    values[1] = 1;
    return fib(n);
}

private int fib(int n) {
    if (n < 1) return 0;
    if (n < 2) return 1;
    int fib1 = fib(n-1);
    int fib2 = values[n-2];
    values[n] = fib1 + fib2;
    return values[n];
}