Rekursive Methode

[Guest]

Hallo, ich soll eine rekursive Methode zur Berechnung von f schreiben, wobei f=n+2 falls n>3 und f=2*f(n-1)+f(n-3) sein soll.
Mein erster Entwurf sieht so aus:

public class Rekursiv {
  static int add(int n){
    if (n<3)
      return n=n+2;
    else
      return n=(2 * add(n-1) + add(n-3));
  }
  public static void main(String[] args) {
    for (int i=0;i<=20;i++){
       System.out.println(add(i));
    }

  }
}

Ist das so richtig?

 

[Johanness]

Ja, eigentlich schon. Nur das "n=" in den returns solltest Du dir schenken.

Also:

public class Rekursiv
{

   static int add(int n){
      if (n<3)
         return n+2;
      else
         return (2 * add(n-1) + add(n-3));
   }
   public static void main(String[] args) {
      for (int i=0;i<=20;i++){
         System.out.println(add(i));
      }

   }

}

Johannes

 

[bygones]

was hält dich davon ab es laufen zu lassen ?

dann siehst du schon obs richtig ist ???

 

[Guest]

Hab ich ja getan. Ich war mir nur nicht sicher, ob das mit der Rekursion so richtig ist bzw ob ich es richtig verstanden habe.

 

[Guest]

Könnte mir jetzt vielleicht noch jemand einen Gedankenanschub liefern, mit dem ich die Methode iterativ schreiben könnte?

 

[Leroy42]

Könnte mir jetzt vielleicht noch jemand einen Gedankenanschub liefern, mit dem ich die Methode iterativ schreiben könnte?

Das glaube ich nicht :cry:
Falls ich mich richtig erinne, kann es keinen allgemeinen Algorithmus geben, der dir
eine beliebige rekursive Funktion in eine iterative mit konstantem Speicherbedarf umwandelt.
Zumindest ist es nicht trivial.

Du kannst die Rekursion zwar unter Hinzunahme eines Stacks iterativ umformen indem
du die Zwischenergebnisse selbst verwaltest, das wäre dann aber nicht wirklich iterativ.

Das heißt allerdings noch lange nicht, daß es für diese spezielle Funktion keine iterative
Lösung gibt. Du könntest dir ja mal eine Tabelle der ersten Funktionswerte erstellen und
versuchen irgendwie herauszubekommen(*), ob es eine Systematik gibt und diese iterativ zu
formulieren. Viel Spaß 8)

==
(*) Das ist zum Beispiel ein Kriterium für wahre Intelligenz (menschlich oder künstlich)

 

[SnooP]

jenau - schau dir die Funktionswerte genau an und überlege dir mal genau was da eigentlich steht beim return, sprich wie berechnet sich der neue Funktionswert... - daraus kannst du dir dann überlegen, wie eine schleife aussehen könnte und wieviel Berechnungsschritte von vorher du jeweils benötigst.. 1, 2, 3... theoretisch unendlich? - falls die Anzahl Berechnungsschritte konstant ist - dann kannst du dir überlegen für diese Anzahl entsprechend viele Variablen zu nutzen, deren Inhalt du jeweils durchreichst pro Schleifendurchlauf um das jetzt mal salopp zu formulieren und nicht zuviel vorweg zunehmen...

keine gute Lösung wäre übrigens nen array zu nehmen und darin die funktionswerte speichern, da damit kein unendlich großes n mehr realisiert werden kann, bzw. viel zu viel Speicherplatz verschwendet wird, wie du recht schnell merken solltest

 

[Bleiglanz]

f=n+2 falls n>3 und f=2*f(n-1)+f(n-3) sein soll.

bei solchen fragen (rekursive zahlenfolge) ist die Antwort immer eine for-schleife

nur muss man dann die werte f_n_minus1 und f_n_minus3 eben "mitschleifen"