Rekursive Methode in Interative Methode umwandeln

[C.B.]

Hallo,

ich möchte diese rekursive Methode in eine Interaktive Methode umwandeln. Durch das zweimalige rekursive aufrufen der a Methode bei x % 2 == 0, weiß ich nicht wie ich vorgehen soll. Habt ihr tipps dazu?

Vielen Dank.

    public static int a(int x, int y) {
        if (x <= 0 || y < 0) {
            return x - y + 2;
        }
        if (x % 2 == 0) {
            return a(x / 2, y) + a(x, y - 1);
        }
        return a(x - 1, y - 2);
    }

 

[Neumi5694]

Du meinst "iterativ". Interaktiv würde ja heißen, dass du während der Laufzeit eingreifen willst.
Davon abgesehen ....

Die erste Bedingung ist offensichtlich dein Rückgabewert ohne Rekursion, die wäre dann also die Abbruchbedingung für egal welche Schleife du verwenden willst.
Der letzte Teil ist das, was bei ungeraden X-Werten innerhalb der Schleife gemacht wird: x und y werden jeweils einfach verändert.
Woran ich im Denken gerade scheitere, ist, wie man den mittleren Teil mit der Addition der beiden rekursiven Aufrufe handhaben könnte.
Das ist eigentlich ein klassisches Beispiel dafür, wo ich auf jeden Fall rekursiv arbeiten würde.

Was soll die Funktion eigentlich berechnen? Die Aufgabe der Funktion iterativ zu lösen wäre sinnvoller als den Code umzuschreiben ohne zu wissen, was rauskommen soll.

    while (x > 0 && y > 0) {
        if (x % 2 == 0) {
            //TODO
        } else {
            x-=1;
            y-"2;
        }
    }
    return x - y + 2;

 

[mihe7]

Woran ich im Denken gerade scheitere, ist, wie man den mittleren Teil mit der Addition der beiden rekursiven Aufrufe handhaben könnte.

Über eine State Machine (besteht hier einfach aus einem boolean): Schritt 1 (false) linke Seite, Schritt 2 (true) rechte Seite und Addition mit der linken Seite. Sollte funktionieren.

Die Aufgabe der Funktion iterativ zu lösen wäre sinnvoller als den Code umzuschreiben ohne zu wissen, was rauskommen soll.

Das ist definitiv der bessere Weg.

 

[C.B.]

Du meinst "iterativ". Interaktiv würde ja heißen, dass du während der Laufzeit eingreifen willst.
Davon abgesehen ....

Die erste Bedingung ist offensichtlich dein Rückgabewert ohne Rekursion, die wäre dann also die Abbruchbedingung für egal welche Schleife du verwenden willst.
Der letzte Teil ist das, was bei ungeraden X-Werten innerhalb der Schleife gemacht wird: x und y werden jeweils einfach verändert.
Woran ich im Denken gerade scheitere, ist, wie man den mittleren Teil mit der Addition der beiden rekursiven Aufrufe handhaben könnte.
Das ist eigentlich ein klassisches Beispiel dafür, wo ich auf jeden Fall rekursiv arbeiten würde.

Was soll die Funktion eigentlich berechnen? Die Aufgabe der Funktion iterativ zu lösen wäre sinnvoller als den Code umzuschreiben ohne zu wissen, was rauskommen soll.

    while (x > 0 && y > 0) {
        if (x % 2 == 0) {
            //TODO
        } else {
            x-=1;
            y-"2;
        }
    }
    return x - y + 2;

Bei mir scheitert es auch am mittleren Teil. Das Umschreiben von rekursiv zu iterativ ist nur zur Übung als Prüfungsvorbereitung.

 

[C.B.]

Über eine State Machine (besteht hier einfach aus einem boolean): Schritt 1 (false) linke Seite, Schritt 2 (true) rechte Seite und Addition mit der linken Seite. Sollte funktionieren.


Das ist definitiv der bessere Weg.

Weiß nicht genau was du meinst, könnest du es noch detaillierter erklären? Vielen Dank.

 

[mihe7]

Das war zu kompliziert von mir gedacht. Hier dürfte ein Stack reichen.

Nehmen wir mal:

public int f(int x) {
    if (x <= 0) { return 0; }
    return x + f(x-1) + f(x/2);
}

Das lässt sich schreiben als:

public int f(int x) {
    if (x <= 0) { return 0; }
    int sum = x;
    sum += f(x-1); // erster rekursiver Aufruf
    sum += f(x/2); // zweiter rekursiver Aufruf
    return sum;
}

Da die Reihenolge der Summanden keine Rolle spielt, kann man hier einfach die Werte auf den Stack legen:

public int f(int x) {
    int sum = 0;
    Stack<Integer> stack = new Stack<>();
    stack.push(x);
    while (!stack.isEmpty()) {
        int cx = stack.pop();
        sum += cx;
        if (cx > 1) {              
             stack.push(cx/2);
        }
        if (cx > 0) {
             stack.push(cx-1);
        }
    }
    return sum;
}

Ansonsten müsste man cx-1 oben und cx/2 unten in den Stack einfügen, dann sollte auch die Reihenfolge passen.

 

[EinNickname9]

Also, bevor man die mathematischen Optimierungen macht, kann man es auch einfach straightforward so machen:

import java.util.Stack;

public class RecursiveToIterative {
    public static int a(int x, int y) {
        if (x <= 0 || y < 0) {
            return x - y + 2;
        }
        if (x % 2 == 0) {
            return a(x / 2, y) + a(x, y - 1);
        }
        return a(x - 1, y - 2);
    }

    public static int b(int x, int y) {
        int result = 0;
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[]{x, y, 0});
        while (!stack.empty()) {
            int[] pop = stack.pop();
            int a = pop[0], b = pop[1];
            if (a <= 0 || b < 0) {
                result = pop[2] + a - b + 2;
            } else if (a % 2 == 0) {
                stack.push(new int[]{a / 2, b, result});
                stack.push(new int[]{a, b - 1, result});
            } else {
                stack.push(new int[]{a - 1, b - 2, result});
            }
        }
        return result;
    }

    public static void main(String[] args) {
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                System.out.println(i + " " + j);
                System.out.println(a(i, j));
                System.out.println(b(i, j));
            }
        }
    }
}

BTW, das Ding heißt "iterativ"!!!

 

[C.B.]

Vielen Dank. Ist das auch mit Feldern umsetzbar? Bin in einem Anfängerkurs und da haben wir Stack nicht behandelt.

 

[EinNickname9]

Ist das auch mit Feldern umsetzbar?

klaro, du musst die Arraygröße nur groß genug wählen und dir dann noch einen Index merken... 🙂

 

[EinNickname9]

stack.push(new int[]{x, y, 0});

in Zeile 17 könnte man auch schreiben: stack.push(new int[]{x, y, result}); das ist vielleicht besser, damit keine magischen Variablen herumschwirren...

 

[C.B.]

klaro, du musst die Arraygröße nur groß genug wählen und dir dann noch einen Index merken... 🙂

D.h. die Methode a und Methode b sind Hilfsmethoden für x und y, da x halbiert wird und y-1 gerechnet wird. Die Ergebnisse der Methoden a und b speichert man in zwei Felder und dann greift man in der Methode f auf die Ergebnisse der Felder zu?

 

[EinNickname9]

D.h. die Methode a und Methode b sind Hilfsmethoden für x und y, da x halbiert wird und y-1 gerechnet wird.

Die genaue Bedeutung dieser Funktionen zu erklären, das ist Sache der Mathematiker. Wir Informatiker sind nur Programmiersklaven oder Erfüllungsgehilfen... also die ganz einfachen Leute, das Fußvolk...

Die Ergebnisse der Methoden a und b speichert man in zwei Felder und dann greift man in der Methode f auf die Ergebnisse der Felder zu?

Nee, Es geht dir doch darum, den "Stack" zu vermeiden, bzw., diesen durch ein Array (int[][]) zu ersetzen. Dafür erstellst du zunächst ein neues Array, sagen wir:
int[][] stack = new int[100][3];
dann brauchst du eine Indexvariable:
int index = 0;
Bei jedem push erhöht sich index um 1. Bei jedem pop verringert es sich um 1. Wenn index <= 0 gilt, dann kann die while-Schleife verlassen werden...

Sage mal, in welchem Anfängerkurs bist du denn? Weil das ist schon etwas fortgeschrittenere Programmierung...

 

[C.B.]

Die genaue Bedeutung dieser Funktionen zu erklären, das ist Sache der Mathematiker. Wir Informatiker sind nur Programmiersklaven oder Erfüllungsgehilfen... also die ganz einfachen Leute, das Fußvolk...


Nee, Es geht dir doch darum, den "Stack" zu vermeiden, bzw., diesen durch ein Array (int[][]) zu ersetzen. Dafür erstellst du zunächst ein neues Array, sagen wir:
int[][] stack = new int[100][3];
dann brauchst du eine Indexvariable:
int index = 0;
Bei jedem push erhöht sich index um 1. Bei jedem pop verringert es sich um 1. Wenn index <= 0 gilt, dann kann die while-Schleife verlassen werden...

Sage mal, in welchem Anfängerkurs bist du denn? Weil das ist schon etwas fortgeschrittenere Programmierung...

Vielen Dank für die Erklärungen. Ich denke wahrscheinlich muss ich das dann nicht können. Es gab immer Aufgaben, wo man eine iterative Methode in eine eine rekursive Lösung und umgekehrt umschreiben musste. Aber da gab es nicht zwei addierte rekursive Aufrufe. Wahrscheinlich muss ich das gar nicht können aber wollte es eben probieren 🙂

 

[Barista]

Es gab immer Aufgaben, wo man eine iterative Methode in eine eine rekursive Lösung und umgekehrt umschreiben musste. Aber da gab es nicht zwei addierte rekursive Aufrufe. Wahrscheinlich muss ich das gar nicht können aber wollte es eben probieren

IMHE kann man nur tail call recursion Aufrufe in eine Iteration umwandeln.

Google Search

Die Verwendung eines expliziten Stack ist IMHE keine wirkliche iterative Lösung.

Mit der Addition wird es deshalb nicht klappen, ist eben die letzte Operation, nicht der rekursive Aufruf.

 

[mihe7]

Die Verwendung eines expliziten Stack ist IMHE keine wirkliche iterative Lösung.

Warum es keine iterative Lösung sein, nur weil einer Datenstruktur verwendet wird?

 

[Barista]

Warum es keine iterative Lösung sein, nur weil einer Datenstruktur verwendet wird?

Du meinst sicher:
Warum soll es keine iterative Lösung sein, nur weil der Stack in einer Datenstruktur verwendet wird?

Dies ist meine subjektive Ansicht.

Ich empfinde in diesem Fall, dass die Umwandlung vom impliziten zum expliziten Stack den rekursiven Charakter der Lösung nicht ändert.

 

[mihe7]

Du meinst sicher:

Sorry, das "r" war zu viel, es sollte heißen, "nur weil eine Datenstruktur verwendet wird". Hier ist die DS ein Stack 🙂

Ich empfinde in diesem Fall, dass die Umwandlung vom impliziten zum expliziten Stack den rekursiven Charakter der Lösung nicht ändert.

Ja, in diesem Fall ist das sicher richtig. In anderen Fällen wirkt das nicht so künstlich, z. B. bei der Tiefensuche in einem Baum. Da führt an einem Stack o.ä. praktisch kein Weg vorbei. Das dürfte problemabhängig sein.

 

[EinNickname9]

Die Verwendung eines expliziten Stack ist IMHE keine wirkliche iterative Lösung.

Ehm, lies einfach nochmal nach, was "rekursiv" und "iterativ" bedeutet - denn diese Ansicht ist falsch. Jede rekursive Form kann mittels Stack in eine iterative gebracht werden.

Das Umformen mathematischer Terme sehe ich hingegen als ungültige iterative Konvertierung an. Bei zum Beispiel den Türmen von Hanoi funktioniert das, ist aber reine mathematische Spielerrei.