Rekursive Algorithmen

[LeifLive]

Liebe Nutzer,

es wäre sehr hilfreich wenn mir jemand etwas Klarheit bei folgenden wohl doch recht einfachen Algorithmen verschaffen könnte, die rekursiv formuliert sind.

Dabei wäre es nett, wenn ihr mir erklären könntet wie viele rekursive Aufrufe es gibt und wie die dann zu dem Gesamtergebnis zusammengeknüpft werden.

Ich habe da 3 Programme, wo mir die Arbeitsweise nicht ganz klar ist:

1) Rechnet GGT aus:

public class Raetsel {

public static int frage(int a, int {

if(b == 0) return a;

return frage(b, a - b * (a/b));

}

}

2) berechnet g hoch r (hier verstehe ich nicht was w sein soll, hat w auch 2

parameter???):

public static double bar(double g, int r) {

if (r < 0)

throw new IllegalArgumentException("does not work");

if (r == 0)

return 1;

else {

double w = bar(g, r / 2);

if (r % 2 != 0)

return w * w * g;

else

return w * w;

}

}

3) berechnet n*n, hier würd ich gerne wissen, ob für n=4 sofort der aufruf

n/2 also 2 wird?

public static int methode(int n) {

if (n == 1) {

return 1;

}

int a = methode(n / 2);

a *= 4;

if (n % 2 == 1) {

a += 2 * n - 1;

}

return a;

}

Ich wäre echt dankbar für Eure Hilfe!!!

[lupo49]

Ich würde dir empfehlen, das ganze nochmal in die CODE-Tags zu packen und außerdem verständlichere Variablennamen zu nehmen. Das erleichtert das ganze schon mal erheblich.

[LeifLive]

Vielen Dank schonmal für eine erste Antwort.

Es handelt sich bei diesen rekursiven Methoden eigentlich um theoretische Aufgaben, wo man die Methode erkennen soll, also erkennen soll was sie macht. Ich habe bereits die Lösung, kann aber halt nicht nachvollziehen weshalb.

Den Code kann ich höchstens noch übersichtlicher darstellen:

Methode berechnet den GGT:

----------------------------

import AlgoTools.IO;

public class Raetsel {

public static int frage(int a, int {

if(b == 0) return a;

return frage(b, a - b * (a/b));

}

}

Methode berechnet g hoch r:

---------------------------

public class Foo {

public static double bar(double g, int r) {

if (r < 0)

throw new IllegalArgumentException("does not work");

if (r == 0)

return 1;

else {

double w = bar(g, r / 2);

if (r % 2 != 0)

return w * w * g;

else

return w * w;

}

}

}

Methode berechnet n*n:

------------------------

public class Fraglich {

public static int methode(int n) {

if (n == 1) {

return 1;

}

int a = methode(n / 2);

a *= 4;

if (n % 2 == 1) {

a += 2 * n - 1;

}

return a;

}

}

Ich hoffe das hilft, bzw. reicht, damit mir jemand erklären kann, wie die rekursiven Aufrufe jeweils gemacht werden, wenn man z.B. in der letzten Aufgabe für den Parameter n = 4 oder so einsetzt. Oh jetzt sehe ich, dass meine veränderte Darstellung nicht übernommen wird, ich hoffe ihr könnt mir es auch so erklären, das wäre sehr nett.

[flashpixx]

Den Code kann ich höchstens noch übersichtlicher darstellen [...] Oh jetzt sehe ich, dass meine veränderte Darstellung nicht übernommen wird, ich hoffe ihr könnt mir es auch so erklären, das wäre sehr nett.

Genau deshalb sollst Du die Code-Tag verwenden !!

[Chief Wiggum]

Genau deshalb sollst Du die Code-Tag verwenden !!

Kurze Bedienungsanleitung:

Entweder im Editorfenster oben im Menüe das Symbol "#" klicken oder den Code (mit allen Einrückungen usw...) in die Tags [ Code] und [ /Code] (Leerzeichen hinter "[" entfernen) einschliessen.

[LeifLive]

Methode berechnet den GGT:

----------------------------


import AlgoTools.IO;


public class Raetsel {


  public static int frage(int a, int  {


    if(b == 0) return a;


    return frage(b, a - b * (a/b));

  }

}

[/code]

[code] Methode berechnet g hoch r: --------------------------- public class Foo { public static double bar(double g, int r) { if (r < 0) throw new IllegalArgumentException("does not work"); if (r == 0) return 1; else { double w = bar(g, r / 2); if (r % 2 != 0) return w * w * g; else return w * w; } } }

Methode berechnet n*n:

------------------------


public class Fraglich {


  public static int methode(int n) {


    if (n == 1) {

       return 1;

    }


   int a = methode(n / 2);

     a *= 4;


   if (n % 2 == 1) {

     a += 2 * n - 1;

   }


 return a;


 }


}

[lupo49]

Wenn du die Algorithmen nicht verstehst, dann geh diese auf einem Blatt Papier für beliebige n einmal durch. Alternativ könntest du dir die Werte mit steigender Rekursionstiefe in einem Java-Debugger anzeigen lassen.

Die Papiervariante ist zu bevorzugen imo.