Methoden Rekursion gibt alten Wert wieder

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:

Meniskusschaden

Top Contributor
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").
 

lollipol27

Mitglied
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:

JStein52

Top Contributor
Ist eigentlich ein Einzeiler:
Code:
    public static int sumup(int x) {
        return (x < 10) ? x : x % 10 + sumup(x / 10);
    }
 

Meniskusschaden

Top Contributor
Also sollte ich die Rekursion in einer variable abspeichern?
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;
 

Meniskusschaden

Top Contributor
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.
 

JStein52

Top Contributor
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)
 

Meniskusschaden

Top Contributor
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.
 

JStein52

Top Contributor
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.
 
X

Xyz1

Gast
Man könnte es wie folgt in eine endrekursive Version umformen:
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.......
 

mrBrown

Super-Moderator
Mitarbeiter
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
 

Flown

Administrator
Mitarbeiter
Ich finde eben nichts offizielles, darum frage ich ja. JVM getuned? Stack auf ein minimum reduziert versucht (habe kein J9)?
 

mrBrown

Super-Moderator
Mitarbeiter
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?


Gibts als Docker-Image ;)
 

Meniskusschaden

Top Contributor
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?
 

mrBrown

Super-Moderator
Mitarbeiter
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. :)
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



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?
Wie gesagt, IBM J9, nicht Java 9 ;)
 
X

Xyz1

Gast
Beim nächsten Mal auch Lesen und Verstehen worum es geht
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.)
 

JStein52

Top Contributor
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;
    }
 
X

Xyz1

Gast
ob das als kürzer gilt
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);
 

JStein52

Top Contributor
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
 

JStein52

Top Contributor
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
 

mrBrown

Super-Moderator
Mitarbeiter
So HIER hab ich die Referenz. J9 implementiert eine TRE (tail-recursion-elimination) und keine vollständige TCO(Tail-call-optimization).

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...

Interessante VM, die jetzt auch auf dem Open-Source-Friedhof liegt.
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...


Ich kann schlecht wissen, welche 3rd-Party du verwendest.
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?
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
J Rekursion über int und array gibt zu wenige Werte zurück Java Basics - Anfänger-Themen 5
K Verstehe Rekursion nicht ganz Java Basics - Anfänger-Themen 7
P Frage zu Rekursion und Backtracking Java Basics - Anfänger-Themen 2
DiyarcanZeren Rekursion in Java Java Basics - Anfänger-Themen 5
M Variablen Rekursion mit 2 Parameteren Java Basics - Anfänger-Themen 4
sserio Rekursion größten Primfaktor finden funktioniert nicht Java Basics - Anfänger-Themen 8
M Lösungsweg Rekursion Java Basics - Anfänger-Themen 1
C StackOverflow bei Rekursion Java Basics - Anfänger-Themen 7
D Rekursion - Ich raffs nicht Java Basics - Anfänger-Themen 16
N Methoden Rekursion mit Kreisen Java Basics - Anfänger-Themen 7
P9cman Vokale in einem String überprüfen mittels Rekursion Java Basics - Anfänger-Themen 8
J Rekursion Java Basics - Anfänger-Themen 22
T Rekursion Programmierverständnis Java Basics - Anfänger-Themen 12
K Rekursion: Rechenmauer mit Array erstellen Java Basics - Anfänger-Themen 17
K Rekursion einer Zahlenfolge (Ab- und Aufzählung) Java Basics - Anfänger-Themen 6
Zeppi Rekursion Java Basics - Anfänger-Themen 15
V Backtracking und Rekursion Java Basics - Anfänger-Themen 15
L REKURSION Java Basics - Anfänger-Themen 13
Kirby.exe Rekursion Java Basics - Anfänger-Themen 7
N for Schleife durch Rekursion ersetzen Java Basics - Anfänger-Themen 6
X Rekursion Java Basics - Anfänger-Themen 3
H Rekursion Java Basics - Anfänger-Themen 2
D Erste Schritte Rekursion Java Basics - Anfänger-Themen 13
M Rekursion Tage Ansteckung gesamte Bevölkerung Java Basics - Anfänger-Themen 15
M Java Rekursion Java Basics - Anfänger-Themen 9
G Java Rekursion Java Basics - Anfänger-Themen 5
J Rekursion Klausur Aufgabe Java Basics - Anfänger-Themen 2
N Rekursion Java Basics - Anfänger-Themen 18
M Verständnisproblem der Rekursion bei Arrays Java Basics - Anfänger-Themen 8
X Rekursion Rätsel Java Basics - Anfänger-Themen 4
N Klassen Rekursion mit Feldern von Objekten Java Basics - Anfänger-Themen 14
W Rekursion Java Basics - Anfänger-Themen 0
D Konsolenausgabe Zahlenfolge Rekursion Java Basics - Anfänger-Themen 3
J Ping Pong Methode mit Rekursion Java Basics - Anfänger-Themen 1
N Rekursion Java Basics - Anfänger-Themen 1
B Rekursion Basic Java Basics - Anfänger-Themen 15
O Rekursion Mergesort Java Basics - Anfänger-Themen 18
G Rekursion Java Basics - Anfänger-Themen 20
M Rekursion Java Basics - Anfänger-Themen 7
F Hilfe bei Rekursion... Java Basics - Anfänger-Themen 4
A Mit Rekursion Zufallszahlen erstellen und größte finden Java Basics - Anfänger-Themen 5
B Rekursion Wurzel Java Basics - Anfänger-Themen 39
O Rekursion ordentlich aufschreiben Java Basics - Anfänger-Themen 2
B Rekursion verstehen Java Basics - Anfänger-Themen 4
O Rekursion Java Basics - Anfänger-Themen 2
E Rekursion verstehen. Java Basics - Anfänger-Themen 4
E Rekursion Kisten befüllen Java Basics - Anfänger-Themen 10
E Rekursion verstehen Java Basics - Anfänger-Themen 2
O Rekursion, String Java Basics - Anfänger-Themen 8
N Invertierte Rekursion??? Java Basics - Anfänger-Themen 5
M Bitte um Hilfe bei Quellcode (Rekursion) Java Basics - Anfänger-Themen 6
T Rekursion Warum bricht meine Funktion nicht ab Java Basics - Anfänger-Themen 4
A Hilfe bei Rekursion,Ich verstehe nicht,wie funktioniert die Rekursion in der Methode "walk" Java Basics - Anfänger-Themen 13
L Rekursion im Baum Java Basics - Anfänger-Themen 9
E Pfade eines Baums angeben ohne Rekursion Java Basics - Anfänger-Themen 20
L Rekursion Baumknoten Java Basics - Anfänger-Themen 8
L Rekursion größtes Zeichen Java Basics - Anfänger-Themen 8
L Rekursion Modulo Java Basics - Anfänger-Themen 7
I Rekursion Java Basics - Anfänger-Themen 11
H Rekursion Java Basics - Anfänger-Themen 7
N Methoden zur Rekursion (catalansche Zahlen) Java Basics - Anfänger-Themen 4
S Frage zu Rekursion... Java Basics - Anfänger-Themen 15
N Java catalansche Zahlen (Rekursion) Java Basics - Anfänger-Themen 5
S Noch eine Frage zur Rekursion... Java Basics - Anfänger-Themen 11
S Frage zu einer Rekursion Java Basics - Anfänger-Themen 15
F Methoden Abbruchbedingung bei Rekursion Java Basics - Anfänger-Themen 2
Z Rekursion Primzahlen Java Basics - Anfänger-Themen 1
K Rekursion Verständnisfrage Java Basics - Anfänger-Themen 19
M Rekursion Minimums Suche Java Basics - Anfänger-Themen 12
J Rekursion Java Basics - Anfänger-Themen 5
F Aufgabe Rekursion Binärer Baum Java Basics - Anfänger-Themen 15
N Rekursion Java Basics - Anfänger-Themen 2
B Rekursion - Übung Java Basics - Anfänger-Themen 2
B Problem beim grundsätzlichen Verständnis bei Rekursion mit 2-dimensionalen Array Java Basics - Anfänger-Themen 6
P Rekursion Java Basics - Anfänger-Themen 19
G Rekursion Beispiel Java Basics - Anfänger-Themen 3
M Rekursion schreiben Java Basics - Anfänger-Themen 16
A Rekursion Funktion in eine Iterativ Funktion umwandeln Java Basics - Anfänger-Themen 9
T Array Rekursion Java Basics - Anfänger-Themen 1
B lineare und schlichte Rekursion Java Basics - Anfänger-Themen 1
A Rekursion Java Basics - Anfänger-Themen 2
B Rekursion Java Basics - Anfänger-Themen 3
A Rekursion stoppt an der falschen Stelle Java Basics - Anfänger-Themen 4
A Lineare Rekursion Java Basics - Anfänger-Themen 6
P Hilfe zur Rekursion? Java Basics - Anfänger-Themen 2
B Rekursion Schneeflocke - Kurze Frage zur Methode Java Basics - Anfänger-Themen 11
L Rekursion Java Basics - Anfänger-Themen 4
S Rekursion Rückgabe - Türme von Hanoi Java Basics - Anfänger-Themen 16
kilopack15 Rekursion und Schleifen Java Basics - Anfänger-Themen 27
E Rekursion Java Basics - Anfänger-Themen 10
G rekursion nicht verstanden Java Basics - Anfänger-Themen 5
K Rekursion-Verständnisfrage Java Basics - Anfänger-Themen 4
E Methoden String wird in Rekursion nicht überschrieben Java Basics - Anfänger-Themen 2
T 2fach Rekursion. Java Basics - Anfänger-Themen 4
N Rekursion mit if-Anweisung Java Basics - Anfänger-Themen 10
K Methoden Zahlensysteme umwandeln mittels Rekursion Java Basics - Anfänger-Themen 5
H Rekursion Binäre Suche Java Basics - Anfänger-Themen 2
P Methoden Primzahltest mit Rekursion Java Basics - Anfänger-Themen 3
C Rekursion überführen in eine normale methode Java Basics - Anfänger-Themen 1
M Methoden Rekursion nachvollziehen Java Basics - Anfänger-Themen 4

Ähnliche Java Themen

Neue Themen


Oben