Rekursion Basic

[BlueLizard]

Hallo Leute,

ich habe glaube ich eine Verständnis Frage was das Thema Rekursion angeht.

Ich habe den Pseudocode gegeben:

if y = 0 then x
    else          f(x-1, y-1)
fi

Nun habe ich also (meiner Meinung nach genau das umgesetzt was mir der Pseudocode sagt:

public static int rec(int x, int y) {
     if (y == 0) return x;
     else {
           System.out.println(y);
           return rec(x-1, y - 1);
     }

Nun mein Problem: Der Algorithmus determiniert nicht für y < 0, obwohl der Pseudocode das verlangt.

Da es eine der ersten Aufgaben dazu ist, wäre ich froh wenn mir jemand nur meinen Denkfehler erklärt, ohne Lösung oder fertigen Code.

Ich danke euch schon mal für die Mühe.

 

[httpdigest]

Der Algorithmus determiniert nicht für y < 0, obwohl der Pseudocode das verlangt.

Wo verlangt der Pseudocode das denn?

 

[insanezulu]

Hallo,
wenn y < 0 gilt, dann kann auch der Pseudocode nicht terminieren, weil y dann immer negativ und nie gleich null ist...
Mit anderen Worten, du hast den Pseudocode genau richtig umgesetzt.

Aber du könntest noch eine Ausgabe für x reinballern.

 

[BlueLizard]

Hallo,
wenn y < 0 gilt, dann kann auch der Pseudocode nicht terminieren, weil y dann immer negativ und nie gleich null ist...
Mit anderen Worten, du hast den Pseudocode genau richtig umgesetzt.

Aber du könntest noch eine Ausgabe für x reinballern.

Genau das ist ja das Problem, ich verstehe es nicht.
Mein Lehrer möchte, dass wenn man ein y < 0 eingibt, das eine Addition gemacht wird, aber ich sehe das in diesem Pseudocode einfach nicht.

Konkret heißt das wenn man x = 454, y = -88 eingibt dann soll 542 raus kommen...

 

[insanezulu]

Naja, dann müsste das etwas umformuliert werden:

if (y <= 0) return x + y;

 

[M.L.]

Konkret heißt das wenn man x = 454, y = -88 eingibt dann soll 542 raus kommen...

Den Pseudocode könnte man erweitern, aber eher um x--y oder x+abs(y)), vgl.mit google.de @ 454--88 oder 454+abs(-88)

 

[mrBrown]

Ich bin mir ziemlich sicher, dass da nirgends ein x+y in irgendeiner Form stehen soll, sondern das ebenso rekursiv gelöst werden soll.
Daher: hast du denn verstanden, was die Funktion für positive Zahlen ausrechnet? Ein Einzelnes Wort reicht als Erklärung

(Da ich nur bedingt Hellsehen kann ist das natürlich etwas Spekulation, die vollständige Aufgabenstellung würde da vielleicht etwas Licht ins Dunkle bringen.)

 

[BlueLizard]

Ich bin mir ziemlich sicher, dass da nirgends ein x+y in irgendeiner Form stehen soll, sondern das ebenso rekursiv gelöst werden soll.
Daher: hast du denn verstanden, was die Funktion für positive Zahlen ausrechnet? Ein Einzelnes Wort reicht als Erklärung

(Da ich nur bedingt Hellsehen kann ist das natürlich etwas Spekulation, die vollständige Aufgabenstellung würde da vielleicht etwas Licht ins Dunkle bringen.)

Da bin ich mir nicht sicher, Meiner Meinung nach soll die Differenz der beiden Zahlen berechnet werden. oder?


Die Aufgabenstellung heißt konkret:
Überlegen Sie, wie der Algorithmus zu erweitern ist, damit er für alle ganzzahligen Werte terminiert.
Schreiben Sie dafür eine Java-Methode

Das heißt für mich das bei einem negativen y statt einer dekrementierung eine inkrementierung erfolgen soll?

 

[kneitzel]

Also bei dem Pseudocode ist kein Datentyp angegeben, daher ist da eigentlich nicht mit einem Overflow zu rechnen. Aber wenn man den umsetzt, dann hat man natürlich die Limitation eines Datentypen und damit einen Overflow.
Leider ist auch der Stack begrenzt, so dass wird bei der Rekursion in ein Problem laufen.

Aber wenn man einen kleinen Datentypen wählt, dann ist das natürlich plötzlich auch lauffähig. Also eine Version mit byte statt int kann man direkt laufen lassen:

package de.javaforum;

public class Recursion {
    public static void main(String[] args) {
        System.out.println(f((byte)10, (byte)-10));
    }

    public static short f(byte x, byte y) {
        if (y == 0) return x;
        return f((byte) (x - 1), (byte) (y - 1));
    }
}

Aber wie gesagt: Bei dem Pseudocode würde ich erst einmal x und y als Ganzzahlen sehen und die haben keine Begrenzung und damit kein Overflow.

 

[mrBrown]

Da bin ich mir nicht sicher, Meiner Meinung nach soll die Differenz der beiden Zahlen berechnet werden. oder?

Jap, und für positive Zahlen klappt's ja auch - musst jetzt nur noch das ganze für negative Y lösen

 

[BlueLizard]

Ich hab jetzt eine Funktion Rec die das tut:

    public static int rec(int x, int y) {

        if (y <= 0) {
            if (y == 0) return x;
            else return rec(x + 1, y + 1);
        }
        if (y >= 0) {
            if (y == 0) return x;
            else return rec(x-1,y -1);
        }
        return 0;
    }

jetzt habe ich mal versucht das selbe iterativ zu formulieren:

      public static int iter(int x, int y) {
        return x-y;
    }

Ist das jetzt das gleiche? Was genau soll mir die Aufgabe jetzt sagen?

 

[mrBrown]

jetzt habe ich mal versucht das selbe iterativ zu formulieren:

      public static int iter(int x, int y) {
        return x-y;
    }

Ist das jetzt das gleiche? Was genau soll mir die Aufgabe jetzt sagen?

Für die iterative Variante müsstest du schon irgendeine Schleife (in die Richtung von while (y>0) ...) einbauen

Was dir die Aufgabe sagen soll, hängt von der Aufgabe ab, die hier niemand kennt ;P
Übersetzen von Pseudocode, erkennen was der Code überhaupt macht, anpassen an andere Fälle, überführen von Rekursion in Iteration, ...

 

[lennero]

Ich hab jetzt eine Funktion Rec die das tut:

    public static int rec(int x, int y) {

        if (y <= 0) {
            if (y == 0) return x;
            else return rec(x + 1, y + 1);
        }
        if (y >= 0) {
            if (y == 0) return x;
            else return rec(x-1,y -1);
        }
        return 0;
    }

jetzt habe ich mal versucht das selbe iterativ zu formulieren:

      public static int iter(int x, int y) {
        return x-y;
    }

Ist das jetzt das gleiche? Was genau soll mir die Aufgabe jetzt sagen?

Beide Methoden machen das Gleiche. Ruf die erste Methode mit y = Integer.MAX_VALUE auf dann siehst du was dir die Aufgabe sagen soll.

 

[mrBrown]

Beide Methoden machen das Gleiche. Ruf die erste Methode mit y = Integer.MAX_VALUE auf dann siehst du was dir die Aufgabe sagen soll.

public class Test {
  public static void main(String[] args) {
      System.out.println(rec(42, Integer.MAX_VALUE));
  }

  public static int rec(int x, int y) {
      if (y <= 0) {
          if (y == 0) return x;
          else return rec(x + 1, y + 1);
      }
      if (y >= 0) {
          if (y == 0) return x;
          else return rec(x-1,y -1);
      }
      return 0;
  }

}

$ javac Test.java
$ java Test
-2147483605

 

[lennero]

public class Test {
  public static void main(String[] args) {
      System.out.println(rec(42, Integer.MAX_VALUE));
  }

  public static int rec(int x, int y) {
      if (y <= 0) {
          if (y == 0) return x;
          else return rec(x + 1, y + 1);
      }
      if (y >= 0) {
          if (y == 0) return x;
          else return rec(x-1,y -1);
      }
      return 0;
  }

}

$ javac Test.java
$ java Test
-2147483605

Bekomme schon mit sehr viel kleineren y-Werten stackoverflow exceptions. Liegts am Betriebssystem?

 

[mrBrown]

Bekomme schon mit sehr viel kleineren y-Werten stackoverflow exceptions. Liegts am Betriebsystem?

An der JVM, OpenJ9 kann (im Gegensatz zur HotSpot VM) tail recursion elimination