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 berechente Binomialkoeffizienten in einem zwei dimensionalen Array zu speichern und vor einem rekursiven Aufruf zu prüfen, ob die Lösung bereits 1x exisitert hat. EInen Array haben wir schon gegeben, mit der perfekten Länge.Dann habe ich mir das überlegt:
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{
return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
if(array[a][b]==0){
array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k);
}
}
}
}
}
}
(Ich hoffe kann man erkennen Tabs sind bisschen verrückt.)
Aber warum funktioniert das nun nicht? Habe doch alles beachtet oder?