ÜbungBaut auf Katas: Listen auf
icon: bi-diagram-3 kind: uebung duration: 1 Doppelstunde languages: [ruby, python, javascript, dart, java] idea: Funktionen, die sich selbst aufrufen, mit einem Fall, der aufhört curriculum: "Oberstufe: Algorithmen und Datenstrukturen (rekursive Verfahren)" topics: [rekursion] requires: [kata-lists]

Katas: Rekursion

Du schreibst Funktionen, die sich selbst aufrufen: die Fakultät, die Summe einer Liste, Fibonacci, die Türme von Hanoi und alle Reihenfolgen eines Textes. Die Prüfung sieht im Code nach, ob deine Funktion sich wirklich selbst aufruft.

1. Ein kleineres Problem derselben Art

Eine rekursive Funktion löst ein Problem, indem sie dasselbe Problem eine Nummer kleiner löst, mit einem Aufruf von sich selbst, und daraus ihr Ergebnis baut. Damit das aufhört, gibt es einen Fall, in dem sie sofort fertig ist. Diese Funktion zählt, wie oft man eine Zahl halbieren kann, bis 1 übrig ist:

def halvings(n)
  return 0 if n <= 1        # sofort fertig
  1 + halvings(n / 2)       # dasselbe, eine Nummer kleiner
end

puts halvings(20)           # 4: 20, 10, 5, 2, 1
def halvings(n):
    if n <= 1:                  # sofort fertig
        return 0
    return 1 + halvings(n // 2) # dasselbe, eine Nummer kleiner

print(halvings(20))             # 4: 20, 10, 5, 2, 1
function halvings(n) {
  if (n <= 1) {                            // sofort fertig
    return 0;
  }
  return 1 + halvings(Math.floor(n / 2));  // dasselbe, eine Nummer kleiner
}

console.log(halvings(20));                 // 4: 20, 10, 5, 2, 1
int halvings(int n) {
  if (n <= 1) {                // sofort fertig
    return 0;
  }
  return 1 + halvings(n ~/ 2); // dasselbe, eine Nummer kleiner
}

void main() {
  print(halvings(20));         // 4: 20, 10, 5, 2, 1
}

~/ teilt ganzzahlig: 5 ~/ 2 ist 2.

int halvings(int n) {
    if (n <= 1) {                  // sofort fertig
        return 0;
    }
    return 1 + halvings(n / 2);    // dasselbe, eine Nummer kleiner
}

void main() {
    IO.println(halvings(20));      // 4: 20, 10, 5, 2, 1
}

Zwei int teilt / ganzzahlig: 5 / 2 ist 2.

halvings(20) wartet auf halvings(10), das auf halvings(5), bis halvings(1) sofort 0 zurückgibt; dann rechnet jeder Aufruf seins dazu, von innen nach außen. Fehlt der Fall, der aufhört, ruft sich die Funktion ohne Ende auf, und das Programm bricht ab, weil der Speicher für die wartenden Aufrufe voll ist.

2. Einstieg

Zum Anfang setzt du wieder eine Funktion aus fertigen Zeilen zusammen. Achte darauf, wo die Rekursion aufhört und womit die Funktion sich selbst aufruft.

Aufgabe 1Quersumme, rekursivEinstieg

Die Quersumme von 1815 ist 1 + 8 + 1 + 5 = 15. Rekursiv gedacht: Die Quersumme ist die letzte Ziffer, n % 10, plus die Quersumme der Zahl ohne die letzte Ziffer, n / 10. Eine einstellige Zahl ist ihre eigene Quersumme. Setz aus den Zeilen eine Funktion digit_sum(n) zusammen, die genau so rechnet: digit_sum(1815) ergibt 15.

Bring die Zeilen in die richtige Reihenfolge und rück sie ein, wo es nötig ist. Nicht jede Zeile gehört dazu: Was nicht passt, lässt du weg. Ziehen geht auch.

  1. 0
  2. def digit_sum(n)
  3. else
  4. end
  5. end
  6. if n < 10
  7. n
  8. n % 10 + digit_sum(n / 10)
  9. n % 10 + digit_sum(n)
Tipp

Erst die Frage, ob die Zahl schon einstellig ist: Dann ist sie selbst das Ergebnis. Sonst kommt die letzte Ziffer plus der Aufruf mit der kürzeren Zahl.

Nächster Tipp

Zwei Zeilen gehören nicht dazu: Eine gibt für eine einstellige Zahl das Falsche zurück, die andere ruft die Funktion mit derselben Zahl wieder auf und hört nie auf.

Aufgabe 1Quersumme, rekursivEinstieg

Die Quersumme von 1815 ist 1 + 8 + 1 + 5 = 15. Rekursiv gedacht: Die Quersumme ist die letzte Ziffer, n % 10, plus die Quersumme der Zahl ohne die letzte Ziffer, n // 10. Eine einstellige Zahl ist ihre eigene Quersumme. Setz aus den Zeilen eine Funktion digit_sum(n) zusammen, die genau so rechnet: digit_sum(1815) ergibt 15.

Bring die Zeilen in die richtige Reihenfolge und rück sie ein, wo es nötig ist. Nicht jede Zeile gehört dazu: Was nicht passt, lässt du weg. Ziehen geht auch.

  1. def digit_sum(n):
  2. if n < 10:
  3. return 0
  4. return n
  5. return n % 10 + digit_sum(n // 10)
  6. return n % 10 + digit_sum(n)
Tipp

Erst die Frage, ob die Zahl schon einstellig ist: Dann ist sie selbst das Ergebnis. Sonst kommt die letzte Ziffer plus der Aufruf mit der kürzeren Zahl.

Nächster Tipp

Zwei Zeilen gehören nicht dazu: Eine gibt für eine einstellige Zahl das Falsche zurück, die andere ruft die Funktion mit derselben Zahl wieder auf und hört nie auf.

Aufgabe 1Quersumme, rekursivEinstieg

Die Quersumme von 1815 ist 1 + 8 + 1 + 5 = 15. Rekursiv gedacht: Die Quersumme ist die letzte Ziffer, n % 10, plus die Quersumme der Zahl ohne die letzte Ziffer, Math.floor(n / 10). Eine einstellige Zahl ist ihre eigene Quersumme. Setz aus den Zeilen eine Funktion digitSum(n) zusammen, die genau so rechnet: digitSum(1815) ergibt 15.

Bring die Zeilen in die richtige Reihenfolge und rück sie ein, wo es nötig ist. Nicht jede Zeile gehört dazu: Was nicht passt, lässt du weg. Ziehen geht auch.

  1. function digitSum(n) {
  2. if (n < 10) {
  3. return 0;
  4. return n % 10 + digitSum(Math.floor(n / 10));
  5. return n % 10 + digitSum(n);
  6. return n;
  7. }
  8. }
Tipp

Erst die Frage, ob die Zahl schon einstellig ist: Dann ist sie selbst das Ergebnis. Sonst kommt die letzte Ziffer plus der Aufruf mit der kürzeren Zahl.

Nächster Tipp

Zwei Zeilen gehören nicht dazu: Eine gibt für eine einstellige Zahl das Falsche zurück, die andere ruft die Funktion mit derselben Zahl wieder auf und hört nie auf.

Aufgabe 1Quersumme, rekursivEinstieg

Die Quersumme von 1815 ist 1 + 8 + 1 + 5 = 15. Rekursiv gedacht: Die Quersumme ist die letzte Ziffer, n % 10, plus die Quersumme der Zahl ohne die letzte Ziffer, n ~/ 10. Eine einstellige Zahl ist ihre eigene Quersumme. Setz aus den Zeilen eine Funktion int digitSum(int n) zusammen, die genau so rechnet: digitSum(1815) ergibt 15.

Bring die Zeilen in die richtige Reihenfolge und rück sie ein, wo es nötig ist. Nicht jede Zeile gehört dazu: Was nicht passt, lässt du weg. Ziehen geht auch.

  1. if (n < 10) {
  2. int digitSum(int n) {
  3. return 0;
  4. return n % 10 + digitSum(n ~/ 10);
  5. return n % 10 + digitSum(n);
  6. return n;
  7. }
  8. }
Tipp

Erst die Frage, ob die Zahl schon einstellig ist: Dann ist sie selbst das Ergebnis. Sonst kommt die letzte Ziffer plus der Aufruf mit der kürzeren Zahl.

Nächster Tipp

Zwei Zeilen gehören nicht dazu: Eine gibt für eine einstellige Zahl das Falsche zurück, die andere ruft die Funktion mit derselben Zahl wieder auf und hört nie auf.

Aufgabe 1Quersumme, rekursivEinstieg

Die Quersumme von 1815 ist 1 + 8 + 1 + 5 = 15. Rekursiv gedacht: Die Quersumme ist die letzte Ziffer, n % 10, plus die Quersumme der Zahl ohne die letzte Ziffer, n / 10. Eine einstellige Zahl ist ihre eigene Quersumme. Setz aus den Zeilen eine Methode int digitSum(int n) zusammen, die genau so rechnet: digitSum(1815) ergibt 15.

Bring die Zeilen in die richtige Reihenfolge und rück sie ein, wo es nötig ist. Nicht jede Zeile gehört dazu: Was nicht passt, lässt du weg. Ziehen geht auch.

  1. if (n < 10) {
  2. int digitSum(int n) {
  3. return 0;
  4. return n % 10 + digitSum(n / 10);
  5. return n % 10 + digitSum(n);
  6. return n;
  7. }
  8. }
Tipp

Erst die Frage, ob die Zahl schon einstellig ist: Dann ist sie selbst das Ergebnis. Sonst kommt die letzte Ziffer plus der Aufruf mit der kürzeren Zahl.

Nächster Tipp

Zwei Zeilen gehören nicht dazu: Eine gibt für eine einstellige Zahl das Falsche zurück, die andere ruft die Funktion mit derselben Zahl wieder auf und hört nie auf.

Aufgabe 2Fakultät, rekursivEinstieg

Die Fakultät kennst du aus den Schleifen: 5! = 5 · 4 · 3 · 2 · 1. Es geht auch so: 5! = 5 · 4!, und 0! = 1. Schreib factorial(n) genau so: Die Funktion ruft sich selbst mit n - 1 auf, bis n 0 ist. factorial(5) ergibt 120. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Zwei Fälle: Wann bist du sofort fertig? Und wie hilft dir factorial(n - 1) sonst?

Nächster Tipp

Ein Gerüst:

def factorial(n)
  return 1 if n == 0
  # n mal die Fakultät von n - 1
end
Aufgabe 2Fakultät, rekursivEinstieg

Die Fakultät kennst du aus den Schleifen: 5! = 5 · 4 · 3 · 2 · 1. Es geht auch so: 5! = 5 · 4!, und 0! = 1. Schreib factorial(n) genau so: Die Funktion ruft sich selbst mit n - 1 auf, bis n 0 ist. factorial(5) ergibt 120. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Zwei Fälle: Wann bist du sofort fertig? Und wie hilft dir factorial(n - 1) sonst?

Nächster Tipp

Ein Gerüst:

def factorial(n):
    if n == 0:
        return 1
    # n mal die Fakultät von n - 1
Aufgabe 2Fakultät, rekursivEinstieg

Die Fakultät kennst du aus den Schleifen: 5! = 5 · 4 · 3 · 2 · 1. Es geht auch so: 5! = 5 · 4!, und 0! = 1. Schreib factorial(n) genau so: Die Funktion ruft sich selbst mit n - 1 auf, bis n 0 ist. factorial(5) ergibt 120. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Zwei Fälle: Wann bist du sofort fertig? Und wie hilft dir factorial(n - 1) sonst?

Nächster Tipp

Ein Gerüst:

function factorial(n) {
  if (n === 0) {
    return 1;
  }
  // n mal die Fakultät von n - 1
}
Aufgabe 2Fakultät, rekursivEinstieg

Die Fakultät kennst du aus den Schleifen: 5! = 5 · 4 · 3 · 2 · 1. Es geht auch so: 5! = 5 · 4!, und 0! = 1. Schreib int factorial(int n) genau so: Die Funktion ruft sich selbst mit n - 1 auf, bis n 0 ist. factorial(5) ergibt 120. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Zwei Fälle: Wann bist du sofort fertig? Und wie hilft dir factorial(n - 1) sonst?

Nächster Tipp

Ein Gerüst:

int factorial(int n) {
  if (n == 0) {
    return 1;
  }
  // n mal die Fakultät von n - 1
}
Aufgabe 2Fakultät, rekursivEinstieg

Die Fakultät kennst du aus den Schleifen: 5! = 5 · 4 · 3 · 2 · 1. Es geht auch so: 5! = 5 · 4!, und 0! = 1. Schreib long factorial(int n) genau so: Die Methode ruft sich selbst mit n - 1 auf, bis n 0 ist. factorial(5) ergibt 120. Sie gibt long zurück, weil 20! nicht mehr in ein int passt. Ohne Schleife: Die Methode ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Zwei Fälle: Wann bist du sofort fertig? Und wie hilft dir factorial(n - 1) sonst?

Nächster Tipp

Ein Gerüst:

long factorial(int n) {
    if (n == 0) {
        return 1;
    }
    // n mal die Fakultät von n - 1
}
Aufgabe 3Die Summe, rekursivEinstieg

Die Summe einer Liste ist ihre erste Zahl plus die Summe des Rests; die leere Liste hat die Summe 0. Schreib total(numbers) so: total([3, 4, 5]) ergibt 12. numbers[1..] ist der Rest der Liste. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wann bist du sofort fertig? Bei der leeren Liste, numbers.empty?.

Nächster Tipp

Sonst: die erste Zahl, numbers[0], plus total vom Rest.

Aufgabe 3Die Summe, rekursivEinstieg

Die Summe einer Liste ist ihre erste Zahl plus die Summe des Rests; die leere Liste hat die Summe 0. Schreib total(numbers) so: total([3, 4, 5]) ergibt 12. numbers[1:] ist der Rest der Liste. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wann bist du sofort fertig? Bei der leeren Liste, not numbers.

Nächster Tipp

Sonst: die erste Zahl, numbers[0], plus total vom Rest.

Aufgabe 3Die Summe, rekursivEinstieg

Die Summe einer Liste ist ihre erste Zahl plus die Summe des Rests; die leere Liste hat die Summe 0. Schreib total(numbers) so: total([3, 4, 5]) ergibt 12. numbers.slice(1) ist der Rest der Liste. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wann bist du sofort fertig? Bei der leeren Liste, numbers.length === 0.

Nächster Tipp

Sonst: die erste Zahl, numbers[0], plus total vom Rest.

Aufgabe 3Die Summe, rekursivEinstieg

Die Summe einer Liste ist ihre erste Zahl plus die Summe des Rests; die leere Liste hat die Summe 0. Schreib int total(List<int> numbers) so: total([3, 4, 5]) ergibt 12. numbers.sublist(1) ist der Rest der Liste. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wann bist du sofort fertig? Bei der leeren Liste, numbers.isEmpty.

Nächster Tipp

Sonst: die erste Zahl, numbers[0], plus total vom Rest.

Aufgabe 3Die Summe, rekursivEinstieg

Die Summe einer Liste ist ihre erste Zahl plus die Summe des Rests; die leere Liste hat die Summe 0. Schreib int total(List<Integer> numbers) so: total(List.of(3, 4, 5)) ergibt 12. numbers.subList(1, numbers.size()) ist der Rest der Liste. Ohne Schleife: Die Methode ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wann bist du sofort fertig? Bei der leeren Liste, numbers.isEmpty().

Nächster Tipp

Sonst: die erste Zahl, numbers.get(0), plus total vom Rest.

Aufgabe 4Countdown, rekursivEinstieg

Schreib countdown(n), die die Liste von n herunter bis 1 zurückgibt: countdown(3) ergibt [3, 2, 1], countdown(0) ergibt []. Der Countdown von 3 ist die 3 und dann der Countdown von 2. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Eine Liste aus einer Zahl ist [n], und + hängt zwei Listen aneinander.

Aufgabe 4Countdown, rekursivEinstieg

Schreib countdown(n), die die Liste von n herunter bis 1 zurückgibt: countdown(3) ergibt [3, 2, 1], countdown(0) ergibt []. Der Countdown von 3 ist die 3 und dann der Countdown von 2. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Eine Liste aus einer Zahl ist [n], und + hängt zwei Listen aneinander.

Aufgabe 4Countdown, rekursivEinstieg

Schreib countdown(n), die die Liste von n herunter bis 1 zurückgibt: countdown(3) ergibt [3, 2, 1], countdown(0) ergibt []. Der Countdown von 3 ist die 3 und dann der Countdown von 2. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Eine Liste aus einer Zahl ist [n], und concat hängt zwei Listen aneinander.

Aufgabe 4Countdown, rekursivEinstieg

Schreib List<int> countdown(int n), die die Liste von n herunter bis 1 zurückgibt: countdown(3) ergibt [3, 2, 1], countdown(0) ergibt []. Der Countdown von 3 ist die 3 und dann der Countdown von 2. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

[n, ...andereListe] ist eine Liste mit n vorn und dahinter den Elementen der anderen.

Aufgabe 4Countdown, rekursivEinstieg

Schreib List<Integer> countdown(int n), die die Liste von n herunter bis 1 zurückgibt: countdown(3) ergibt [3, 2, 1], countdown(0) eine leere Liste. Der Countdown von 3 ist die 3 und dann der Countdown von 2. Ohne Schleife: Die Methode ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Eine neue ArrayList, zuerst add(n), dann addAll(countdown(n - 1)): So steht n vorn.

Aufgabe 5Wie lang, ohne zu messen?Einstieg

Schreib text_length(text), die die Zeichen eines Textes zählt, ohne length und size; text[1..] ist der Text ohne sein erstes Zeichen: Ein leerer Text hat die Länge 0, jeder andere ist um eins länger als der Text ohne sein erstes Zeichen. text_length('Hallo') ergibt 5. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wann bist du sofort fertig? Beim leeren Text, ''.

Nächster Tipp

Sonst: 1 plus die Länge des Rests.

Aufgabe 5Wie lang, ohne zu messen?Einstieg

Schreib text_length(text), die die Zeichen eines Textes zählt, ohne len; text[1:] ist der Text ohne sein erstes Zeichen: Ein leerer Text hat die Länge 0, jeder andere ist um eins länger als der Text ohne sein erstes Zeichen. text_length('Hallo') ergibt 5. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wann bist du sofort fertig? Beim leeren Text, ''.

Nächster Tipp

Sonst: 1 plus die Länge des Rests.

Aufgabe 5Wie lang, ohne zu messen?Einstieg

Schreib textLength(text), die die Zeichen eines Textes zählt, ohne length; text.slice(1) ist der Text ohne sein erstes Zeichen: Ein leerer Text hat die Länge 0, jeder andere ist um eins länger als der Text ohne sein erstes Zeichen. textLength('Hallo') ergibt 5. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wann bist du sofort fertig? Beim leeren Text, ''.

Nächster Tipp

Sonst: 1 plus die Länge des Rests.

Aufgabe 5Wie lang, ohne zu messen?Einstieg

Schreib int textLength(String text), die die Zeichen eines Textes zählt, ohne length; text.substring(1) ist der Text ohne sein erstes Zeichen: Ein leerer Text hat die Länge 0, jeder andere ist um eins länger als der Text ohne sein erstes Zeichen. textLength('Hallo') ergibt 5. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wann bist du sofort fertig? Beim leeren Text, text.isEmpty.

Nächster Tipp

Sonst: 1 plus die Länge des Rests.

Aufgabe 5Wie lang, ohne zu messen?Einstieg

Schreib int textLength(String text), die die Zeichen eines Textes zählt, ohne length(); text.substring(1) ist der Text ohne sein erstes Zeichen: Ein leerer Text hat die Länge 0, jeder andere ist um eins länger als der Text ohne sein erstes Zeichen. textLength("Hallo") ergibt 5. Ohne Schleife: Die Methode ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wann bist du sofort fertig? Beim leeren Text, text.isEmpty().

Nächster Tipp

Sonst: 1 plus die Länge des Rests.

3. Übung

Aufgabe 6PotenzÜbung

Schreib power(base, exponent) für einen Exponenten ab 0: power(2, 10) ergibt 1024. Jede Zahl hoch 0 ist 1, und base hoch n ist base mal base hoch n - 1. Ohne ** und pow. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wie bei der Fakultät: ein Fall, in dem du sofort fertig bist, und einer, der sich selbst mit einer kleineren Zahl aufruft.

Aufgabe 6PotenzÜbung

Schreib power(base, exponent) für einen Exponenten ab 0: power(2, 10) ergibt 1024. Jede Zahl hoch 0 ist 1, und base hoch n ist base mal base hoch n - 1. Ohne ** und pow. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wie bei der Fakultät: ein Fall, in dem du sofort fertig bist, und einer, der sich selbst mit einer kleineren Zahl aufruft.

Aufgabe 6PotenzÜbung

Schreib power(base, exponent) für einen Exponenten ab 0: power(2, 10) ergibt 1024. Jede Zahl hoch 0 ist 1, und base hoch n ist base mal base hoch n - 1. Ohne ** und Math.pow. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wie bei der Fakultät: ein Fall, in dem du sofort fertig bist, und einer, der sich selbst mit einer kleineren Zahl aufruft.

Aufgabe 6PotenzÜbung

Schreib int power(int base, int exponent) für einen Exponenten ab 0: power(2, 10) ergibt 1024. Jede Zahl hoch 0 ist 1, und base hoch n ist base mal base hoch n - 1. Ohne pow. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wie bei der Fakultät: ein Fall, in dem du sofort fertig bist, und einer, der sich selbst mit einer kleineren Zahl aufruft.

Aufgabe 6PotenzÜbung

Schreib int power(int base, int exponent) für einen Exponenten ab 0: power(2, 10) ergibt 1024. Jede Zahl hoch 0 ist 1, und base hoch n ist base mal base hoch n - 1. Ohne Math.pow. Ohne Schleife: Die Methode ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wie bei der Fakultät: ein Fall, in dem du sofort fertig bist, und einer, der sich selbst mit einer kleineren Zahl aufruft.

Aufgabe 7Fibonacci, rekursivÜbung

Jede Fibonacci-Zahl ist die Summe der beiden davor; die nullte ist 0, die erste 1. Schreib fibonacci(n) genau so, mit zwei Aufrufen von sich selbst: fibonacci(10) ergibt 55. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Zwei Zahlen stehen fest, fibonacci(0) und fibonacci(1). Jede andere ist fibonacci(n - 1) + fibonacci(n - 2).

Aufgabe 7Fibonacci, rekursivÜbung

Jede Fibonacci-Zahl ist die Summe der beiden davor; die nullte ist 0, die erste 1. Schreib fibonacci(n) genau so, mit zwei Aufrufen von sich selbst: fibonacci(10) ergibt 55. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Zwei Zahlen stehen fest, fibonacci(0) und fibonacci(1). Jede andere ist fibonacci(n - 1) + fibonacci(n - 2).

Aufgabe 7Fibonacci, rekursivÜbung

Jede Fibonacci-Zahl ist die Summe der beiden davor; die nullte ist 0, die erste 1. Schreib fibonacci(n) genau so, mit zwei Aufrufen von sich selbst: fibonacci(10) ergibt 55. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Zwei Zahlen stehen fest, fibonacci(0) und fibonacci(1). Jede andere ist fibonacci(n - 1) + fibonacci(n - 2).

Aufgabe 7Fibonacci, rekursivÜbung

Jede Fibonacci-Zahl ist die Summe der beiden davor; die nullte ist 0, die erste 1. Schreib int fibonacci(int n) genau so, mit zwei Aufrufen von sich selbst: fibonacci(10) ergibt 55. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Zwei Zahlen stehen fest, fibonacci(0) und fibonacci(1). Jede andere ist fibonacci(n - 1) + fibonacci(n - 2).

Aufgabe 7Fibonacci, rekursivÜbung

Jede Fibonacci-Zahl ist die Summe der beiden davor; die nullte ist 0, die erste 1. Schreib int fibonacci(int n) genau so, mit zwei Aufrufen von sich selbst: fibonacci(10) ergibt 55. Ohne Schleife: Die Methode ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Zwei Zahlen stehen fest, fibonacci(0) und fibonacci(1). Jede andere ist fibonacci(n - 1) + fibonacci(n - 2).

Ausprobieren: Ruf deine Funktion fibonacci mit 25, 30 und 35 auf und schau, wie lange es jeweils dauert. Warum wird es so schnell langsamer? Zähl einmal, wie oft fibonacci(2) aufgerufen wird, wenn du fibonacci(6) ausrechnest.
Aufgabe 8Palindrom, rekursivÜbung

Ein Text ist ein Palindrom, wenn sein erstes und sein letztes Zeichen gleich sind und das, was dazwischen steht, wieder ein Palindrom ist; ein Text mit weniger als zwei Zeichen ist immer eins. Schreib palindrome(text) so, ohne den Text umzudrehen: palindrome('rentner') ergibt true. Die Texte sind klein geschrieben. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

text[0] ist das erste Zeichen, text[-1] das letzte, text[1...-1] das, was dazwischen steht.

Aufgabe 8Palindrom, rekursivÜbung

Ein Text ist ein Palindrom, wenn sein erstes und sein letztes Zeichen gleich sind und das, was dazwischen steht, wieder ein Palindrom ist; ein Text mit weniger als zwei Zeichen ist immer eins. Schreib palindrome(text) so, ohne den Text umzudrehen: palindrome('rentner') ergibt True. Die Texte sind klein geschrieben. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

text[0] ist das erste Zeichen, text[-1] das letzte, text[1:-1] das, was dazwischen steht.

Aufgabe 8Palindrom, rekursivÜbung

Ein Text ist ein Palindrom, wenn sein erstes und sein letztes Zeichen gleich sind und das, was dazwischen steht, wieder ein Palindrom ist; ein Text mit weniger als zwei Zeichen ist immer eins. Schreib palindrome(text) so, ohne den Text umzudrehen: palindrome('rentner') ergibt true. Die Texte sind klein geschrieben. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

text[0] ist das erste Zeichen, text[text.length - 1] das letzte, text.slice(1, -1) das, was dazwischen steht.

Aufgabe 8Palindrom, rekursivÜbung

Ein Text ist ein Palindrom, wenn sein erstes und sein letztes Zeichen gleich sind und das, was dazwischen steht, wieder ein Palindrom ist; ein Text mit weniger als zwei Zeichen ist immer eins. Schreib bool palindrome(String text) so, ohne den Text umzudrehen: palindrome('rentner') ergibt true. Die Texte sind klein geschrieben. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

text[0] ist das erste Zeichen, text[text.length - 1] das letzte, text.substring(1, text.length - 1) das, was dazwischen steht.

Aufgabe 8Palindrom, rekursivÜbung

Ein Text ist ein Palindrom, wenn sein erstes und sein letztes Zeichen gleich sind und das, was dazwischen steht, wieder ein Palindrom ist; ein Text mit weniger als zwei Zeichen ist immer eins. Schreib boolean palindrome(String text) so, ohne den Text umzudrehen: palindrome("rentner") ergibt true. Die Texte sind klein geschrieben. Ohne Schleife: Die Methode ruft sich selbst auf; die Prüfung sieht nach.

Tipp

text.charAt(0) ist das erste Zeichen, text.charAt(text.length() - 1) das letzte, text.substring(1, text.length() - 1) das, was dazwischen steht. Zeichen (char) vergleicht man mit ==.

Aufgabe 9Wie oft kommt es vor?Übung

Schreib count_char(text, char), die zählt, wie oft das Zeichen char im Text steht: count_char('banane', 'n') ergibt 2. Wie bei der Länge, nur zählt das erste Zeichen nur dann, wenn es char ist. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wie text_length, nur zählt das erste Zeichen 1 oder 0.

Aufgabe 9Wie oft kommt es vor?Übung

Schreib count_char(text, char), die zählt, wie oft das Zeichen char im Text steht: count_char('banane', 'n') ergibt 2. Wie bei der Länge, nur zählt das erste Zeichen nur dann, wenn es char ist. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wie text_length, nur zählt das erste Zeichen 1 oder 0.

Aufgabe 9Wie oft kommt es vor?Übung

Schreib countChar(text, char), die zählt, wie oft das Zeichen char im Text steht: countChar('banane', 'n') ergibt 2. Wie bei der Länge, nur zählt das erste Zeichen nur dann, wenn es char ist. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wie textLength, nur zählt das erste Zeichen 1 oder 0.

Aufgabe 9Wie oft kommt es vor?Übung

Schreib int countChar(String text, String letter), die zählt, wie oft das Zeichen letter im Text steht: countChar('banane', 'n') ergibt 2. Wie bei der Länge, nur zählt das erste Zeichen nur dann, wenn es letter ist. Ohne Schleife: Die Funktion ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wie textLength, nur zählt das erste Zeichen 1 oder 0: (text[0] == letter ? 1 : 0).

Aufgabe 9Wie oft kommt es vor?Übung

Schreib int countChar(String text, char letter), die zählt, wie oft das Zeichen letter im Text steht: countChar("banane", 'n') ergibt 2. Ein einzelnes Zeichen, ein char, steht in einfachen Anführungszeichen. Wie bei der Länge, nur zählt das erste Zeichen nur dann, wenn es letter ist. Ohne Schleife: Die Methode ruft sich selbst auf; die Prüfung sieht nach.

Tipp

Wie textLength, nur zählt das erste Zeichen 1 oder 0: (text.charAt(0) == letter ? 1 : 0).

4. Knobelei

Aufgabe 10Die Türme von HanoiKnobelei

Auf dem Stab source liegen n Scheiben, die größte unten. Sie sollen auf den Stab target; eine Scheibe nach der anderen, nie eine größere auf eine kleinere, und spare hilft. Schreib hanoi(n, source, target, spare), die die Züge als Liste zurückgibt, jeden Zug als Paar [von, nach]: hanoi(2, 'A', 'C', 'B') ergibt [['A', 'B'], ['A', 'C'], ['B', 'C']]. Der Trick: Die oberen n - 1 Scheiben sind ein kleinerer Turm.

Tipp

Drei Schritte: den Turm aus n - 1 Scheiben aus dem Weg räumen, die größte Scheibe ziehen, den kleineren Turm wieder darauf.

Nächster Tipp

Wohin kommt der kleinere Turm zuerst, und welcher Stab hilft ihm dabei? Jeder Schritt ist ein Aufruf von hanoi mit anderen Stäben.

Aufgabe 10Die Türme von HanoiKnobelei

Auf dem Stab source liegen n Scheiben, die größte unten. Sie sollen auf den Stab target; eine Scheibe nach der anderen, nie eine größere auf eine kleinere, und spare hilft. Schreib hanoi(n, source, target, spare), die die Züge als Liste zurückgibt, jeden Zug als Paar [von, nach]: hanoi(2, 'A', 'C', 'B') ergibt [['A', 'B'], ['A', 'C'], ['B', 'C']]. Der Trick: Die oberen n - 1 Scheiben sind ein kleinerer Turm.

Tipp

Drei Schritte: den Turm aus n - 1 Scheiben aus dem Weg räumen, die größte Scheibe ziehen, den kleineren Turm wieder darauf.

Nächster Tipp

Wohin kommt der kleinere Turm zuerst, und welcher Stab hilft ihm dabei? Jeder Schritt ist ein Aufruf von hanoi mit anderen Stäben.

Aufgabe 10Die Türme von HanoiKnobelei

Auf dem Stab source liegen n Scheiben, die größte unten. Sie sollen auf den Stab target; eine Scheibe nach der anderen, nie eine größere auf eine kleinere, und spare hilft. Schreib hanoi(n, source, target, spare), die die Züge als Liste zurückgibt, jeden Zug als Paar [von, nach]: hanoi(2, 'A', 'C', 'B') ergibt [['A', 'B'], ['A', 'C'], ['B', 'C']]. Der Trick: Die oberen n - 1 Scheiben sind ein kleinerer Turm.

Tipp

Drei Schritte: den Turm aus n - 1 Scheiben aus dem Weg räumen, die größte Scheibe ziehen, den kleineren Turm wieder darauf.

Nächster Tipp

Wohin kommt der kleinere Turm zuerst, und welcher Stab hilft ihm dabei? Jeder Schritt ist ein Aufruf von hanoi mit anderen Stäben.

Aufgabe 10Die Türme von HanoiKnobelei

Auf dem Stab source liegen n Scheiben, die größte unten. Sie sollen auf den Stab target; eine Scheibe nach der anderen, nie eine größere auf eine kleinere, und spare hilft. Schreib List<List<String>> hanoi(int n, String source, String target, String spare), die die Züge als Liste zurückgibt, jeden Zug als Paar [von, nach]: hanoi(2, 'A', 'C', 'B') ergibt [['A', 'B'], ['A', 'C'], ['B', 'C']]. Der Trick: Die oberen n - 1 Scheiben sind ein kleinerer Turm.

Tipp

Drei Schritte: den Turm aus n - 1 Scheiben aus dem Weg räumen, die größte Scheibe ziehen, den kleineren Turm wieder darauf.

Nächster Tipp

Wohin kommt der kleinere Turm zuerst, und welcher Stab hilft ihm dabei? Jeder Schritt ist ein Aufruf von hanoi mit anderen Stäben; [...a, zug, ...b] setzt die Züge zusammen.

Aufgabe 10Die Türme von HanoiKnobelei

Auf dem Stab source liegen n Scheiben, die größte unten. Sie sollen auf den Stab target; eine Scheibe nach der anderen, nie eine größere auf eine kleinere, und spare hilft. Schreib List<List<String>> hanoi(int n, String source, String target, String spare), die die Züge als Liste zurückgibt, jeden Zug als Paar List.of(von, nach): hanoi(2, "A", "C", "B") ergibt [[A, B], [A, C], [B, C]]. Der Trick: Die oberen n - 1 Scheiben sind ein kleinerer Turm.

Tipp

Drei Schritte: den Turm aus n - 1 Scheiben aus dem Weg räumen, die größte Scheibe ziehen, den kleineren Turm wieder darauf.

Nächster Tipp

Wohin kommt der kleinere Turm zuerst, und welcher Stab hilft ihm dabei? Jeder Schritt ist ein Aufruf von hanoi mit anderen Stäben; addAll hängt seine Züge an, add(List.of(source, target)) den Zug der größten Scheibe.

Aufgabe 11Listen in ListenKnobelei

In einer Liste können wieder Listen stehen, beliebig tief: [1, [2, [3, 4]], 5]. Schreib flatten(items), die alle Zahlen in einer flachen Liste zurückgibt, in ihrer Reihenfolge: [1, 2, 3, 4, 5]. Ohne flatten.

Tipp

Geh die Elemente durch. item.is_a?(Array) fragt, ob ein Element selbst eine Liste ist.

Nächster Tipp

Ist es eine, machst du sie mit flatten flach, bevor sie ins Ergebnis kommt.

Aufgabe 11Listen in ListenKnobelei

In einer Liste können wieder Listen stehen, beliebig tief: [1, [2, [3, 4]], 5]. Schreib flatten(items), die alle Zahlen in einer flachen Liste zurückgibt, in ihrer Reihenfolge: [1, 2, 3, 4, 5]. Ohne eine fertige Funktion.

Tipp

Geh die Elemente durch. isinstance(item, list) fragt, ob ein Element selbst eine Liste ist.

Nächster Tipp

Ist es eine, machst du sie mit flatten flach, bevor sie ins Ergebnis kommt.

Aufgabe 11Listen in ListenKnobelei

In einer Liste können wieder Listen stehen, beliebig tief: [1, [2, [3, 4]], 5]. Schreib flatten(items), die alle Zahlen in einer flachen Liste zurückgibt, in ihrer Reihenfolge: [1, 2, 3, 4, 5]. Ohne flat.

Tipp

Geh die Elemente durch. Array.isArray(item) fragt, ob ein Element selbst eine Liste ist.

Nächster Tipp

Ist es eine, machst du sie mit flatten flach, bevor sie ins Ergebnis kommt.

Aufgabe 11Listen in ListenKnobelei

In einer Liste können wieder Listen stehen, beliebig tief: [1, [2, [3, 4]], 5]. Schreib List<int> flatten(List<Object> items), die alle Zahlen in einer flachen Liste zurückgibt, in ihrer Reihenfolge: [1, 2, 3, 4, 5]. Ohne expand.

Tipp

Geh die Elemente durch. item is List fragt, ob ein Element selbst eine Liste ist, item is int, ob es eine Zahl ist.

Nächster Tipp

Ist es eine Liste, machst du sie mit flatten(item.cast<Object>()) flach und hängst das Ergebnis mit addAll an.

Aufgabe 11Listen in ListenKnobelei

In einer Liste können wieder Listen stehen, beliebig tief: [1, [2, [3, 4]], 5]. Schreib List<Integer> flatten(List<?> items), die alle Zahlen in einer flachen Liste zurückgibt, in ihrer Reihenfolge: [1, 2, 3, 4, 5]. List<?> ist eine Liste, in der alles Mögliche stehen kann.

Tipp

Geh die Elemente durch, for (Object item : items). item instanceof List<?> inner fragt, ob ein Element selbst eine Liste ist, und nennt sie gleich inner; item instanceof Integer n ebenso für eine Zahl.

Nächster Tipp

Ist es eine Liste, machst du sie mit flatten(inner) flach und hängst das Ergebnis mit addAll an.

Aufgabe 12Alle ReihenfolgenKnobelei

Schreib permutations(text), die alle Reihenfolgen der Zeichen zurückgibt: permutations('abc') ergibt ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']. Der Reihe nach kommt jedes Zeichen einmal nach vorn, und dahinter stehen alle Reihenfolgen der übrigen. Der leere Text hat eine Reihenfolge, ['']. Ohne permutation.

Tipp

Für jedes Zeichen: Nimm es heraus, text[0...i] + text[(i + 1)..] ist der Rest, und setz es vor jede Reihenfolge des Rests.

Nächster Tipp

Eine Schleife über die Zeichen darfst du hier benutzen; die Rekursion steckt in permutations(rest).

Aufgabe 12Alle ReihenfolgenKnobelei

Schreib permutations(text), die alle Reihenfolgen der Zeichen zurückgibt: permutations('abc') ergibt ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']. Der Reihe nach kommt jedes Zeichen einmal nach vorn, und dahinter stehen alle Reihenfolgen der übrigen. Der leere Text hat eine Reihenfolge, ['']. Ohne itertools.permutations.

Tipp

Für jedes Zeichen: Nimm es heraus, text[:i] + text[i + 1:] ist der Rest, und setz es vor jede Reihenfolge des Rests.

Nächster Tipp

Eine Schleife über die Zeichen darfst du hier benutzen; die Rekursion steckt in permutations(rest).

Aufgabe 12Alle ReihenfolgenKnobelei

Schreib permutations(text), die alle Reihenfolgen der Zeichen zurückgibt: permutations('abc') ergibt ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']. Der Reihe nach kommt jedes Zeichen einmal nach vorn, und dahinter stehen alle Reihenfolgen der übrigen. Der leere Text hat eine Reihenfolge, ['']. Ohne eine fertige Funktion.

Tipp

Für jedes Zeichen: Nimm es heraus, text.slice(0, i) + text.slice(i + 1) ist der Rest, und setz es vor jede Reihenfolge des Rests.

Nächster Tipp

Eine Schleife über die Zeichen darfst du hier benutzen; die Rekursion steckt in permutations(rest).

Aufgabe 12Alle ReihenfolgenKnobelei

Schreib List<String> permutations(String text), die alle Reihenfolgen der Zeichen zurückgibt: permutations('abc') ergibt ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']. Der Reihe nach kommt jedes Zeichen einmal nach vorn, und dahinter stehen alle Reihenfolgen der übrigen. Der leere Text hat eine Reihenfolge, [''].

Tipp

Für jedes Zeichen: Nimm es heraus, text.substring(0, i) + text.substring(i + 1) ist der Rest, und setz es vor jede Reihenfolge des Rests.

Nächster Tipp

Eine Schleife über die Zeichen darfst du hier benutzen; die Rekursion steckt in permutations(rest).

Aufgabe 12Alle ReihenfolgenKnobelei

Schreib List<String> permutations(String text), die alle Reihenfolgen der Zeichen zurückgibt: permutations("abc") ergibt [abc, acb, bac, bca, cab, cba]. Der Reihe nach kommt jedes Zeichen einmal nach vorn, und dahinter stehen alle Reihenfolgen der übrigen. Der leere Text hat eine Reihenfolge: eine Liste mit dem leeren Text.

Tipp

Für jedes Zeichen: Nimm es heraus, text.substring(0, i) + text.substring(i + 1) ist der Rest, und setz es vor jede Reihenfolge des Rests: text.charAt(i) + order.

Nächster Tipp

Eine Schleife über die Zeichen darfst du hier benutzen; die Rekursion steckt in permutations(rest).

5. Extras Extra

Ein Extra für Schnelle: Die Seite ist ohne dieses Kapitel vollständig.

Zwei Katas, die nicht mitzählen. Bei der ersten zählt auch, wie schnell dein Code ist.

Aufgabe 13Fibonacci mit GedächtnisExtra

Deine rekursive Fibonacci-Funktion rechnet dieselben Zahlen wieder und wieder aus: fibonacci(70) dauert mehr als ein halbes Jahr. Schreib fast_fibonacci(n), rekursiv wie vorher, aber mit einem Gedächtnis: einem Hash, in dem jede Zahl steht, sobald sie einmal ausgerechnet ist. fast_fibonacci(70) ergibt 190392490709135, in weniger als drei Sekunden.

Tipp

Ein Hash außerhalb der Funktion, MEMO = {}, merkt sich die Zahlen. Steht n schon darin, gibst du sie gleich zurück.

Nächster Tipp

MEMO[n] ||= … rechnet nur, wenn MEMO[n] noch fehlt, und schreibt das Ergebnis hinein.

Aufgabe 13Fibonacci mit GedächtnisExtra

Deine rekursive Fibonacci-Funktion rechnet dieselben Zahlen wieder und wieder aus: fibonacci(70) dauert fast ein Jahr. Schreib fast_fibonacci(n), rekursiv wie vorher, aber mit einem Gedächtnis: einem Dictionary, in dem jede Zahl steht, sobald sie einmal ausgerechnet ist. fast_fibonacci(70) ergibt 190392490709135, in weniger als drei Sekunden.

Tipp

Ein Dictionary außerhalb der Funktion, memo = {}, merkt sich die Zahlen. Steht n schon darin, gibst du sie gleich zurück.

Nächster Tipp

Erst nachsehen (n in memo), sonst rechnen und hineinschreiben.

Aufgabe 13Fibonacci mit GedächtnisExtra

Deine rekursive Fibonacci-Funktion rechnet dieselben Zahlen wieder und wieder aus: fibonacci(70) dauert Wochen. Schreib fastFibonacci(n), rekursiv wie vorher, aber mit einem Gedächtnis: einem Objekt, in dem jede Zahl steht, sobald sie einmal ausgerechnet ist. fastFibonacci(70) ergibt 190392490709135, in weniger als drei Sekunden.

Tipp

Ein Objekt außerhalb der Funktion, const memo = {};, merkt sich die Zahlen. Steht n schon darin, gibst du sie gleich zurück.

Nächster Tipp

Erst nachsehen (n in memo), sonst rechnen und hineinschreiben.

Aufgabe 13Fibonacci mit GedächtnisExtra

Deine rekursive Fibonacci-Funktion rechnet dieselben Zahlen wieder und wieder aus: fibonacci(70) dauert Wochen. Schreib int fastFibonacci(int n), rekursiv wie vorher, aber mit einem Gedächtnis: einer Map, in der jede Zahl steht, sobald sie einmal ausgerechnet ist. fastFibonacci(70) ergibt 190392490709135, in wenigen Sekunden.

Tipp

Eine Map außerhalb der Funktion, final memo = <int, int>{};, merkt sich die Zahlen. Steht n schon darin, gibst du sie gleich zurück.

Nächster Tipp

Erst nachsehen (memo.containsKey(n)), sonst rechnen und hineinschreiben.

Aufgabe 13Fibonacci mit GedächtnisExtra

Deine rekursive Fibonacci-Methode rechnet dieselben Zahlen wieder und wieder aus: fibonacci(70) dauert Wochen. Schreib long fastFibonacci(int n), rekursiv wie vorher, aber mit einem Gedächtnis: einer Map, in der jede Zahl steht, sobald sie einmal ausgerechnet ist. fastFibonacci(70) ergibt 190392490709135, in wenigen Sekunden.

Tipp

Eine Map außerhalb der Methode, Map<Integer, Long> memo = new HashMap<>();, merkt sich die Zahlen. Steht n schon darin, gibst du sie gleich zurück.

Nächster Tipp

Erst nachsehen (memo.containsKey(n)), sonst rechnen und mit memo.put(n, …) hineinschreiben.

Aufgabe 14Geht die Summe auf?Extra

Schreib subset_sum(numbers, target), die true zurückgibt, wenn einige der Zahlen zusammen genau target ergeben, jede höchstens einmal, und sonst false: subset_sum([3, 34, 4, 12, 5, 2], 9) ergibt true (4 + 5). Für die erste Zahl gibt es zwei Möglichkeiten: Sie ist dabei, oder nicht. Die Zahlen sind größer als 0.

Tipp

Zwei Fälle, in denen du sofort fertig bist: target ist 0 (dann ja), oder es sind keine Zahlen mehr übrig (dann nein).

Nächster Tipp

Sonst: mit der ersten Zahl, subset_sum(rest, target - numbers[0]), oder ohne sie, subset_sum(rest, target). Geht eins davon, geht es.

Aufgabe 14Geht die Summe auf?Extra

Schreib subset_sum(numbers, target), die True zurückgibt, wenn einige der Zahlen zusammen genau target ergeben, jede höchstens einmal, und sonst False: subset_sum([3, 34, 4, 12, 5, 2], 9) ergibt True (4 + 5). Für die erste Zahl gibt es zwei Möglichkeiten: Sie ist dabei, oder nicht. Die Zahlen sind größer als 0.

Tipp

Zwei Fälle, in denen du sofort fertig bist: target ist 0 (dann ja), oder es sind keine Zahlen mehr übrig (dann nein).

Nächster Tipp

Sonst: mit der ersten Zahl, subset_sum(rest, target - numbers[0]), oder ohne sie, subset_sum(rest, target). Geht eins davon, geht es.

Aufgabe 14Geht die Summe auf?Extra

Schreib subsetSum(numbers, target), die true zurückgibt, wenn einige der Zahlen zusammen genau target ergeben, jede höchstens einmal, und sonst false: subsetSum([3, 34, 4, 12, 5, 2], 9) ergibt true (4 + 5). Für die erste Zahl gibt es zwei Möglichkeiten: Sie ist dabei, oder nicht. Die Zahlen sind größer als 0.

Tipp

Zwei Fälle, in denen du sofort fertig bist: target ist 0 (dann ja), oder es sind keine Zahlen mehr übrig (dann nein).

Nächster Tipp

Sonst: mit der ersten Zahl, subsetSum(rest, target - numbers[0]), oder ohne sie, subsetSum(rest, target). Geht eins davon, geht es.

Aufgabe 14Geht die Summe auf?Extra

Schreib bool subsetSum(List<int> numbers, int target), die true zurückgibt, wenn einige der Zahlen zusammen genau target ergeben, jede höchstens einmal, und sonst false: subsetSum([3, 34, 4, 12, 5, 2], 9) ergibt true (4 + 5). Für die erste Zahl gibt es zwei Möglichkeiten: Sie ist dabei, oder nicht. Die Zahlen sind größer als 0.

Tipp

Zwei Fälle, in denen du sofort fertig bist: target ist 0 (dann ja), oder es sind keine Zahlen mehr übrig (dann nein).

Nächster Tipp

Sonst: mit der ersten Zahl, subsetSum(rest, target - numbers[0]), oder ohne sie, subsetSum(rest, target). Geht eins davon, geht es.

Aufgabe 14Geht die Summe auf?Extra

Schreib boolean subsetSum(List<Integer> numbers, int target), die true zurückgibt, wenn einige der Zahlen zusammen genau target ergeben, jede höchstens einmal, und sonst false: subsetSum(List.of(3, 34, 4, 12, 5, 2), 9) ergibt true (4 + 5). Für die erste Zahl gibt es zwei Möglichkeiten: Sie ist dabei, oder nicht. Die Zahlen sind größer als 0.

Tipp

Zwei Fälle, in denen du sofort fertig bist: target ist 0 (dann ja), oder es sind keine Zahlen mehr übrig (dann nein).

Nächster Tipp

Sonst: mit der ersten Zahl, subsetSum(rest, target - numbers.get(0)), oder ohne sie, subsetSum(rest, target), mit rest = numbers.subList(1, numbers.size()). Geht eins davon, geht es.