Methoden Rekursion gibt alten Wert wieder

L

lollipol27

Mitglied
Hallo Leute,

folgendes Problem: ich versuche ein Programm zu schreiben, um die iterierte Quersumme zu bekommen (Vorgehensweise siehe hier: https://www.cachewiki.de/wiki/Quersumme). Mein Problem liegt jetzt allerdings darin, dass mein Programm scheinbar den richtigen Wert berechnet, aber den Wert aus dem vorletzten Rekursionsschritt wiedergibt. Ich weiß allerdings nicht, woher es diesen Wert wieder nimmt und wieso das überhaupt passiert. Bin für jede Hilfe dankbar!
Java: 
public class quer{

    public static void main(String[] lol){
        int number = Integer.parseInt(lol[0]);
        int ausgabe = 0;

        if (number > 9){
            ausgabe = sumup(number);
        }
        System.out.println("Die iterierte Quersumme ist " + ausgabe);
    }
  

    public static int sumup(int number){
        int sum = 0;
      
        while (number > 0){
            sum += number % 10;
            number /= 10;
        }
        number = sum;
      
        if (number > 9){
            sumup(number);
        }
      
        return number;
    }
}
Liebe Grüße
lollipol27
 
Zuletzt bearbeitet von einem Moderator:
Der rekursive Aufruf von sumup() ist nutzlos, weil du das Ergebnis gar nicht verwertest.

PS: Bitte verwende Code-Tags für den Quellcode (z.B. über den Button "Einfügen").
 
Java: 
public class quer {

  public static void main(String[] lol) {
    int number = Integer.parseInt(lol[0]);
    int ausgabe = 0;

    if (number > 9) {
      ausgabe = sumup(number);
    }
    System.out.println("Die iterierte Quersumme ist " + ausgabe);
  }


  public static int sumup(int number) {
    int sum = 0;

    while (number > 0) {
      sum += number % 10;
      number /= 10;
    }
    number = sum;

    if (number > 9) {
      sumup(number);
    }

    return number;
  }
}
Also sollte ich die Rekursion in einer variable abspeichern?
 
Zuletzt bearbeitet von einem Moderator:
Ist eigentlich ein Einzeiler:
Code: 
    public static int sumup(int x) {
        return (x < 10) ? x : x % 10 + sumup(x / 10);
    }
 
lollipol27 hat gesagt.:
Also sollte ich die Rekursion in einer variable abspeichern?
Zum Vergrößern anklicken....
Das wäre eine Möglichkeit, aber nicht die einzige. Entscheidend ist eben, dass du das richtige Ergebnis an den Aufrufer zurück lieferst. Welchen Wert liefert return number; denn in folgendem Fragment zurück, wenn number zunächst beispielsweise den Wert 12 hat?
Java: 
if (number > 9){
    sumup(number);
}
return number;
 
Zu Beginn hat number den Wert 12. Wenn return number zum Schluss 3 zurück liefern würde, müsste number ja in den dazwischen liegenden Zeilen verändert worden sein. Wo soll das denn passiert sein? Da steht doch keine Anweisung, die number verändert.
number ist eine lokale Variable. Für die Dauer jeden Methodenaufrufs existiert eine eigene Version davon. Wenn es durch rekursive Aufrufe gleichzeitig mehrere nicht beendete Aufrufe derselben Methode gibt, hat jede ihre eigene Version von number, die nichts mit den jeweils anderen zu tun hat.
 
Und zur Berechnung der iterierten Quersumme gibt es jetzt zwei einfache Wege.
1.) ein Schleifchen um die einfacher Quersumme:
Code: 
    public static int quersumme(int x) {
        return (x < 10)
                ? x
                : x % 10 + quersumme(x / 10);
    }

    public static int iterierteQuersumme(int zahl) {
        int iterierteQuersumme = zahl;
        while (0 != zahl) {
            iterierteQuersumme = quersumme(iterierteQuersumme);
            zahl = zahl / 10;
        }
        return iterierteQuersumme;
    }

2.) du machst dir folgende Bemerkung aus deinem Link zu Nutze:
Die iterierte Quersumme ist identisch zur Modulo 9 Berechnung, also den Rest bei der Division durch 9 (außer wenn die iterierte Quersumme 9 ist, dann ist der Wert der Modulo 9 Berechnung 0)
 
Man könnte es wie folgt in eine endrekursive Version umformen:
Java: 
    public static int sumup(int x, int s) {
        return (x<10) ? x+s : sumup(x/10, x%10+s);
    }
Für den Aufruf sumup(123456789, 0) würde man dann immer noch 45 erhalten.
Mit "Reinziehen" ist also gemeint, dass die Addition von x%10 nicht nach der Rückkehr aus dem rekursiven Aufruf erfolgt, sondern noch innerhalb des Aufrufs.
 
Ja, vereinfacht dem Compiler die Optimierung in eine iterative Variante. Aber für die Quersumme ??? Ich weiss ja nicht. Diese Variante reduziert die Lesbarkeit ja schon ... vor allem wenn man noch ein bisschen Probleme mit Rekursion hat wie es beim TE wohl der Fall ist.
 
Meniskusschaden hat gesagt.:
Man könnte es wie folgt in eine endrekursive Version umformen:
Zum Vergrößern anklicken....
Danke für die endrekursive-Variante...
Ich kann mich erinnern, in einer Prüfung mit der Frage, formen Sie in endrekursiv um wenn nicht bereits endrekursiv, mit der Antwort "bereits endrekursiv" die Frage falsch beantwortet zu haben (war aber auch nicht zur Einsicht gegangen...).
Das ist, wie @mrBrown richtigerweise erwähnt, damit optimiert werden kann, bzw., vielleicht schon bereits optimiert ist.
Aber es zählt auch Lesbarkeit anstatt Optimierung....... Allzu lang ist so eine Zahl ja auch nicht.......
 
Ehrlich gesagt, keine Ahnung. Mit google findet man bestimmt irgendwas offizielles von IBM dazu...


Im Zweifel einfach mal testen 😉

Java: 
class Tail {
    public static void main(String... args) {
      long n = tailRec(0,100_000);
      System.out.println(n);

      long m = rec(100_000);
      System.out.println(m);
    }

    static long tailRec(long acc, long n){
        if (n == 0) return acc;
        return tailRec(1 + acc, n - 1);
    }

    static long rec(long n){
        if (n == 0) return 0;
        return 1 + rec(n - 1);
    }
}

Auf der Oracle-JVM gibt beides nen StackOverflow, auf der J9 nur die nicht-Endrekursive Variante
 
Ich finde eben nichts offizielles, darum frage ich ja. JVM getuned? Stack auf ein minimum reduziert versucht (habe kein J9)?
 
Beides ohne jegliche Konfiguration.
An der Stack-Größe liegt’s nicht, die ist für jeweils beide Varianten gleich, allerdings kann nur die Endrekursive Variante (theoretisch) unendlich tief sein.

Was sollte auch dagegen sprechen, das da auf die Art optimiert wird?


Flown hat gesagt.:
habe kein J9?
Zum Vergrößern anklicken....
Gibts als Docker-Image 😉
 
Bei mir kommt es auch mit Java 9 zum StackOverflow. Vielleicht lässt es sich durch Ausgabe des Stacktrace weiter plausibilisieren. Müßte der in der endrekursiven Variante bei @mrBrown nicht konstant bleiben, falls die Optimierung stattfindet?
 
DerWissende hat gesagt.:
Wollte keine Diskussion auslösen....
Kurze Suche:
https://www.google.de/search?q=java+9+tail+call+optimization
https://softwareengineering.stackex...a-have-optimization-for-tail-recursion-at-all
https://stackoverflow.com/questions...-jvm-still-not-support-tail-call-optimization

Sieht nicht danach aus.... Evtl kann @mrBrown 's JVM mit einer Rekusiontiefe von 100_000 einfach besser handlen. Baue es mal in infinitem Regress um. 🙂
Zum Vergrößern anklicken....
Beim nächsten Mal auch Lesen und Verstehen worum es geht - nicht um Java 9, sondern um IBMs J9, die in den Links übrigens erwähnt wird, weil sie es kann.

https://softwareengineering.stackex...or-tail-recursion-at-all#comment556020_272083
https://stackoverflow.com/questions...ail-call-optimization?answertab=votes#tab-top



Meniskusschaden hat gesagt.:
Bei mir kommt es auch mit Java 9 zum StackOverflow. Vielleicht lässt es sich durch Ausgabe des Stacktrace weiter plausibilisieren. Müßte der in der endrekursiven Variante bei @mrBrown nicht konstant bleiben, falls die Optimierung stattfindet?
Zum Vergrößern anklicken....
Wie gesagt, IBM J9, nicht Java 9 😉
 
mrBrown hat gesagt.:
Beim nächsten Mal auch Lesen und Verstehen worum es geht
Zum Vergrößern anklicken....
Irgendwie habe ich das Gefühl, du hättest nicht verstanden, um was es ging, wenn ich nach einer endrekursiven-Variante gefragt hätte...
Ich kann schlecht wissen, welche 3rd-Party du verwendest.
Wies auch sei, das weicht ganz stark von der eigentlichen Fragestellung und der Umsetzung mit zwei geschachtelten Schleifen ab.
Java: 
        int summe = 111163; // hier der Wert
        do
            for (int i = summe, t = (summe = 0); i != 0; summe += i % 10, i /= 10) 
                ;
        while (summe != 1 && summe != 4);
        System.out.println(summe);

Kürzer geht nicht, Ausgabe sollte 4 sein. (Leerzeilen sind natürlich en Geschmacksfrage.)
 
Keine Ahnung ob das als kürzer gilt:
Code: 
    public static int iterierteQuersumme1(int zahl) {
        int iterierteQuersumme = 0;
        iterierteQuersumme = zahl % 9;
        return (iterierteQuersumme == 0) ? 9 : iterierteQuersumme;
    }
 
JStein52 hat gesagt.:
ob das als kürzer gilt
Zum Vergrößern anklicken....
Das ist die kurze (kürzeste) Schreibweise für rekursiv, und das ist die kürzeste Schreibweise für iterativ:
Java: 
        int summe = 111163;
        do for (int i = summe, t = (summe = 0); i != 0; summe += i % 10, i /= 10); while (summe != 1 && summe != 4);
        System.out.println(summe);
 
Und warum ist das kürzer als meines ? Zählst du da die bentzten Zeichen/Buchstaben ? Dann kann ich es nämlich auch noch ein bisschen quetschen indem ich die Variable iterierteQuersumme weglasse

Edit: btw. da ist nichts rekursiv bei mir. Obacht, die Variable heisst so wie die Methode !! Ist aber kein rekursiver Aufruf
 
Um es dir noch besser zu verdeutlichen:
Code: 
    public static int iterierteQuersumme1(int zahl) {
        zahl= zahl % 9;
        return (zahl== 0) ? 9 : zahl;
    }
keine Schleifen, keine Iteration
 
Flown hat gesagt.:
So HIER hab ich die Referenz. J9 implementiert eine TRE (tail-recursion-elimination) und keine vollständige TCO(Tail-call-optimization).
Zum Vergrößern anklicken....

Danke für die Referenz 😉

Eben um TRE ginge ja hier auch, aber wer weiß, vielleicht kommt ja noch TCO, Funktionaler wird's ja schon...

Flown hat gesagt.:
Interessante VM, die jetzt auch auf dem Open-Source-Friedhof liegt.
Zum Vergrößern anklicken....
Abwarten, ob sich das als Friedhof herausstellt 😉 Ich kann mir schon vorstellen, das IBM die weiterhin entwickelt und für eigene Produkte benutzt. Hotspot läuft ja zB mWn nicht auf z/OS.

Vllt profitiert auch Hotspot davon...


DerWissende hat gesagt.:
Ich kann schlecht wissen, welche 3rd-Party du verwendest.
Zum Vergrößern anklicken....
Du meinst, weil dazu sagen, dass ich nicht die Hotspot-JVM, sondern die J9 meine, nicht reicht, um zu wissen, dass ich nicht die Hotspot-JVM, sondern die J9 meine? Hätte ich lieber noch mal dazu sagen sollen, das ich nicht die Hotspot-JVM, sondern die J9 meine?
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

ich will die alten "alte JButtons"wieder haben
Antworten: 6
JButton werden richtig gewechselt aber die Maus macht die alten wieder Sichtbar??
Antworten: 5
In alten Code zurück- und dort wieder zurechtfinden?
Antworten: 17
alten Container wieder aufrufen
Antworten: 11
JTable überschreibt alten Wert
Antworten: 12

Zurück
Oben