ÜbungBaut auf Katas: Listen auf

icon: bi-diagram-3 kind: uebung duration: 1 Doppelstunde languages: [ruby, python, javascript] idea: Funktionen, die sich selbst aufrufen, mit einem Fall, der aufhört curriculum: "Oberstufe: Algorithmen und Datenstrukturen (rekursive Verfahren)" 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

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

Aufgabe 1Fakultä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.

def factorial(n)
end

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 1Fakultät, rekursivEinstieg

def factorial(n):
    pass

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 1Fakultät, rekursivEinstieg

function factorial(n) {
}

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

def total(numbers)
end

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

def total(numbers):
    pass

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

function total(numbers) {
}

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 3Countdown, 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.

def countdown(n)
end

Tipp

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

Aufgabe 3Countdown, rekursivEinstieg

def countdown(n):
    pass

Tipp

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

Aufgabe 3Countdown, rekursivEinstieg

function countdown(n) {
}

Tipp

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

Aufgabe 4Wie 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.

def text_length(text)
end

Tipp

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

Nächster Tipp

Sonst: 1 plus die Länge des Rests.

Aufgabe 4Wie 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.

def text_length(text):
    pass

Tipp

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

Nächster Tipp

Sonst: 1 plus die Länge des Rests.

Aufgabe 4Wie 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.

function textLength(text) {
}

Tipp

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

Nächster Tipp

Sonst: 1 plus die Länge des Rests.

3. Übung

Aufgabe 5PotenzÜ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.

def power(base, exponent)
end

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 5PotenzÜbung

def power(base, exponent):
    pass

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 5PotenzÜ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.

function power(base, exponent) {
}

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 6Fibonacci, 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.

def fibonacci(n)
end

Tipp

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

Aufgabe 6Fibonacci, rekursivÜbung

def fibonacci(n):
    pass

Tipp

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

Aufgabe 6Fibonacci, rekursivÜbung

function fibonacci(n) {
}

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

def palindrome(text)
end

Tipp

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

Aufgabe 7Palindrom, 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.

def palindrome(text):
    pass

Tipp

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

Aufgabe 7Palindrom, rekursivÜbung

function palindrome(text) {
}

Tipp

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

Aufgabe 8Wie 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.

def count_char(text, char)
end

Tipp

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

Aufgabe 8Wie oft kommt es vor?Übung

def count_char(text, char):
    pass

Tipp

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

Aufgabe 8Wie 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.

function countChar(text, char) {
}

Tipp

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

4. Knobelei

Aufgabe 9Die 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.

def hanoi(n, source, target, spare)
end

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 9Die Türme von HanoiKnobelei

def hanoi(n, source, target, spare):
    pass

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 9Die Türme von HanoiKnobelei

function hanoi(n, source, target, spare) {
}

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

def flatten(items)
end

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 10Listen in ListenKnobelei

def flatten(items):
    pass

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 10Listen in ListenKnobelei

function flatten(items) {
}

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

def permutations(text)
end

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 11Alle ReihenfolgenKnobelei

def permutations(text):
    pass

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 11Alle ReihenfolgenKnobelei

function permutations(text) {
}

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

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 12Fibonacci mit GedächtnisExtra

Deine rekursive Fibonacci-Funktion rechnet dieselben Zahlen wieder und wieder aus: fibonacci(70) dauert Jahre. 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.

def fast_fibonacci(n)
end

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 12Fibonacci mit GedächtnisExtra

Deine rekursive Fibonacci-Funktion rechnet dieselben Zahlen wieder und wieder aus: fibonacci(70) dauert Jahre. 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.

def fast_fibonacci(n):
    pass

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 12Fibonacci mit GedächtnisExtra

Deine rekursive Fibonacci-Funktion rechnet dieselben Zahlen wieder und wieder aus: fibonacci(70) dauert Jahre. 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.

function fastFibonacci(n) {
}

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

def subset_sum(numbers, target)
end

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

def subset_sum(numbers, target):
    pass

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

function subsetSum(numbers, target) {
}

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.