Recurison

Adriano10

Bekanntes Mitglied
Code:
    @Override
    public int count(int[] coins, int money) {
        if (money < 0) {
            throw new IllegalArgumentException("Amount of money must be positive! Expected: >= 0, found: " + money + ".");
        }
        if (coins == null || coins.length == 0) {
            throw new IllegalArgumentException("At least one coin option must be given!");
        }
        for (int coin : coins) {
            if (coin <= 0) {
                throw new IllegalArgumentException("Coin values must be positive! Expected: > 0, found: " + coin + ".");
            }
        }
        return count(coins, money, coins.length - 1);
    }

    private int count(int[] coins, int money, int index) {
        if (money < 0) {
            return 0;
        }
        if (money == 0) {
            return 1;
        }
        if (index < 0) {
            return 0;
        }
        return count(coins, money, index - 1) + count(coins, money - coins[index], index);
    }
    public static void main(String[] args) {
        üben u = new üben();
        int[] coins1 = new int[] { 1, 2, 5 };
        int result = u.count(coins1, 5);
        System.out.println(result);
    

}

Ich habe Probleme mit Recursion, könnte jemand mir ein Gefallen tun und erklären, wie man " return count(coins, money, index - 1) + count(coins, money - coins[index], index);" lesen kann?

Ich danke im Voraus
 

Adriano10

Bekanntes Mitglied
Naja, genau so, wie es da steht :)

Java:
int teilergebnis1 = count(coins, money, index - 1);
int teilergebnis2 = count(coins, money - count[index], index);
return teilergebnis1 + teilergebnis2;
Danke für die Anwort.

Dieses erste Teil ist mir ganz unklar
int teilergebnis1 = count(coins, money, index - 1);

was passiert hier, wenn index = coins.length = 3; ?
 

Adriano10

Bekanntes Mitglied
Naja, genau so, wie es da steht :)

Java:
int teilergebnis1 = count(coins, money, index - 1);
int teilergebnis2 = count(coins, money - count[index], index);
return teilergebnis1 + teilergebnis2;
teilergebnis1 teilergebnis2
2 ///////////////// 3
1 /////////////// 3
0 // ////////////// 4

und Ausgabe ist 4:
hab ich richtig verstanden?
 

mihe7

Top Contributor
Nein, weil das Ergebnis nicht nur von index sondern auch von coins und money abhängig ist.

Die Frage ist: was zählt coins (ganz unabhängig von der Rekursion)?
 

mihe7

Top Contributor
Fangen wir mal andersrum an. Das Problem, das viele mit der Rekursion haben, ist zu verstehen, dass der rekursive Methoenaufruf sich nicht von anderen Methodenaufrufen unterscheidet, sondern ein ganz gewöhnlicher Aufruf ist.

Wir könnten z. B. die Fakultät berechnen. Dazu schreiben wir uns erst einmal eine Methode, die die Fakultät von n-1 berechnet - nicht rekursiv:
Java:
public int fakMinus1(int n) {
    int result = 1;
    for (int i = 2; i < n; i++) {
        result *= i;
    }
    return result;
}
Wenn wir also die Fakultät von (5-1) wissen wollen, können wir fakMinus1(5) aufrufen. Wenn wir das Ergebnis noch mit 5 multiplizieren, erhalten wir die Fakultät von 5. Allgemein: wenn wir n*fakMinus1(n) rechnen, erhalten wir die Fakultät von n.
Java:
public int fak(int n) {
    return n * fakMinus1(n);
}
Hier gibt es keine Rekursion: fak ruft einfach fakMinus1 auf, um die Fakultät von n-1 zu erhalten, nimmt das Ergebnis mal n und berechnet so die Fakultät von n.

Jetzt kommt der Trick: wenn fak die Fakultät von n berechnet, dann müsste man ja nur fak(n-1) rechnen, um die Fakultät von n-1 zu erhalten. Wir könnten also prinzipiell fakMinus1 durch fak(n-1) ersetzen.
Java:
public int fak(int n) {
    return n * fak(n-1);
}
Damit haben wir allerdings ein Problem, denn fak(n-1) wird in jedem Aufruf immer wieder aufgerufen - wir haben eine Endlosrekursion. Wir müssen den Spaß also begrenzen und das erreichen wir im Prinzip genauso wie in fakMinus1. Dort haben wir nämlich stillschweigend vorausgesetzt, dass die Fakultät von 0 gleich 1 ist, indem wir mit result = 1 begonnen haben.

Also noch die Begrenzung einbauen:
Java:
public int fak(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * fak(n-1);
    }
}
Die Tatsache, dass wir negative Werte nicht abfangen, schenken wir uns einfach mal, denn hier geht es ums Prinzip. Es macht nun gar keinen Unterschied, ob Du fak(n-1) in einer x-beliebigen Methode oder in fak selbst aufrufst: das Ergebnis ist immer die Fakultät von n-1.

Wenn Du fak(5) aufrufst, wird berechnet:
Code:
Aufruf fak(5) = 5 * fak(4) 
  Aufruf fak(4) = 4 * fak(3)
    Aufruf fak(3) = 3 * fak(2)
      Aufruf fak(2) = 2 * fak(1)
        Aufruf fak(1) = 1 * fak(0)
          Aufruf fak(0) = hier wird nicht weiter aufgerufen, aufgrund des if-Statements.

Jetzt kehren wir von den Aufrufen wieder zurück:

          Rückgabe fak(0) = 1 (if-Statement)
        Rückgabe fak(1) = 1 * 1 = 1
      Rückgabe fak(2) = 2 * 1 = 2
    Rückgabe fak(3) = 3 * 2 = 6
  Rückgabe fak(4) = 4 * 6 = 24
Rückgabe fak(5) = 5 * 24 = 120
 

Neue Themen


Oben