Übungsaufgaben zu Rekursion und Iteration

Bewertung: Testfall 1 2 Punkte, Testfälle 2 und 3 je 1 Punkt.

Nachvollzug für Testfall 1 (Aufrufebenen):

Fehler (2 Punkte): Die Bezeichnung wird vor dem rekursiven Aufruf ausgegeben, also beim Abstieg. Die Prozedur beginnt bei der Kategorie des Artikels und läuft zur Hauptkategorie hinauf; deshalb erscheint die unterste Kategorie zuerst und der Pfad steht in umgekehrter Reihenfolge. Hauptkategorien (Testfall 3) sind nicht betroffen.

Korrektur (2 Punkte): Erst die Oberkategorien ausgeben lassen (rekursiver Aufruf), danach – beim Aufstieg – das Trennzeichen und die eigene Bezeichnung:

JANA Pseudo-Pascal Pseudo-Pascal (deutsch) Pseudo-Python all none

zeigePfad(int id) {
    if (oberId[id] != 0) {
        zeigePfad(oberId[id])
        write(" > ")
    }
    write(bezeichnung[id])
}

PROCEDURE zeigePfad(id: integer)
    if (oberId[id] <> 0) then
        zeigePfad(oberId[id])
        write(" > ")
    end if
    write(bezeichnung[id])
END zeigePfad

Prozedur zeigePfad(id: integer)
    wenn oberId[id] <> 0 dann
        zeigePfad(oberId[id])
        Ausgabe " > "
    Ende wenn
    Ausgabe bezeichnung[id]
Ende zeigePfad

def zeigePfad(id):
    if oberId[id] != 0:
        zeigePfad(oberId[id])
        print(" > ", end="")
    # Ende if
    print(bezeichnung[id], end="")
# Ende zeigePfad

Andere korrekte Korrekturen sind ebenfalls richtig, z. B. eine rekursive Funktion, die den Pfad als Zeichenkette zurückgibt: Rückgabe pfad(oberId[id]) & " > " & bezeichnung[id].

• Jeder Aufruf erhält auf dem Aufrufstapel einen eigenen Stapelrahmen mit seinem Parameter id und der Rücksprungadresse. Die Ebenen haben daher unterschiedliche Werte von id (12, 11, 3, 1), ohne sich gegenseitig zu überschreiben. (1 Punkt)

• Beim Abstieg ruft zeigePfad(12) die Prozedur mit 11 auf, diese mit 3, diese mit 1. Die aufrufenden Ebenen warten, ihre Rahmen bleiben liegen. (1 Punkt)

• zeigePfad(1) erreicht die Abbruchbedingung (oberId[1] = 0), gibt Fahrräder aus und wird als erstes beendet; ihr Rahmen wird vom Stapel entfernt. Beim Aufstieg setzt jede Ebene hinter ihrem Aufruf fort, gibt > und ihre Bezeichnung aus und wird beendet (Last In, First Out). (1 Punkt)

• Größte Aufruftiefe: 4 gleichzeitig offene Aufrufe (= Anzahl der Ebenen im Pfad). (1 Punkt)

Ablauf (2 Punkte): Die Kategorie verweist auf sich selbst. oberId[14] <> 0 ist immer wahr, daher ruft sich zeigePfad(14) immer wieder mit derselben ID auf; das Problem wird nicht kleiner, die Abbruchbedingung wird nie erreicht (Endlosrekursion). Jeder Aufruf legt einen neuen Stapelrahmen an, bis der Stapelspeicher voll ist: Stapelüberlauf (in Java StackOverflowError), die Seite wird nicht angezeigt bzw. der Dienst bricht ab. Es wird nichts ausgegeben, weil die Ausgaben erst beim Aufstieg erfolgen.

Maßnahmen (je 1 Punkt, zwei verlangt):

• Daten beim Import und in der Datenbank prüfen, z. B. CHECK (ober_kategorie_id <> kategorie_id); längere Zyklen (13 → 7 → 13) erkennt erst eine Prüfung beim Import, die den Pfad bis zur Hauptkategorie verfolgt.

• Eine maximale Tiefe als zusätzlichen Parameter mitgeben (zeigePfad(id, restTiefe), Abbruch mit Fehlermeldung bei restTiefe = 0).

• Bereits besuchte IDs merken und bei einer Wiederholung abbrechen.

• Iterative Fassung mit Schleifenzähler verwenden (verhindert den Stapelüberlauf, aber nicht die Endlosschleife – nur zusammen mit einer Obergrenze sinnvoll).

Je 2 Punkte für eine Beschreibung mit Begründung, z. B.:

• Vorteil: Die rekursive Lösung ist kurz und leicht verständlich, weil sie die Struktur des Problems direkt abbildet („erst der Pfad der Oberkategorie, dann die eigene Bezeichnung“). Die Umkehr der Reihenfolge erledigt der Aufrufstapel; eine Hilfsdatenstruktur ist nicht nötig.

• Nachteil: Für jeden Aufruf wird ein Stapelrahmen angelegt. Die rekursive Lösung braucht daher mehr Arbeitsspeicher und durch die Aufrufe etwas mehr Rechenzeit; bei großer Tiefe oder fehlerhaften Daten droht ein Stapelüberlauf.

Ebenfalls richtig: schwerer zu debuggen bzw. nachzuvollziehen (Vorgänge auf mehreren Ebenen gleichzeitig), Korrektheit lässt sich wie ein Induktionsbeweis begründen (Vorteil).

JANA Pseudo-Pascal Pseudo-Pascal (deutsch) Pseudo-Python all none

zeigePfad(int id) {
    Stapel s = new Stapel()
    int aktuell = id
    while (aktuell != 0) {                     // bis über die Hauptkategorie hinaus
        s.ablegen(bezeichnung[aktuell])
        aktuell = oberId[aktuell]
    }
    write(s.entnehmen())                       // Hauptkategorie ohne Trennzeichen
    while (!s.istLeer()) {
        write(" > " + s.entnehmen())
    }
}

PROCEDURE zeigePfad(id: integer)
    s: Stapel := new Stapel()
    aktuell: integer := id
    while (aktuell <> 0) do                    // bis über die Hauptkategorie hinaus
        s.ablegen(bezeichnung[aktuell])
        aktuell := oberId[aktuell]
    end while
    write(s.entnehmen())                       // Hauptkategorie ohne Trennzeichen
    while (NOT s.istLeer()) do
        write(" > " & s.entnehmen())
    end while
END zeigePfad

Prozedur zeigePfad(id: integer)
    s: Stapel := new Stapel()
    aktuell: integer := id
    solange aktuell <> 0                       // bis über die Hauptkategorie hinaus
        s.ablegen(bezeichnung[aktuell])
        aktuell := oberId[aktuell]
    Ende solange
    Ausgabe s.entnehmen()                      // Hauptkategorie ohne Trennzeichen
    solange nicht s.istLeer()
        Ausgabe " > " & s.entnehmen()
    Ende solange
Ende zeigePfad

def zeigePfad(id):
    s = Stapel()
    aktuell = id
    while aktuell != 0:                        # bis über die Hauptkategorie hinaus
        s.ablegen(bezeichnung[aktuell])
        aktuell = oberId[aktuell]
    # Ende while
    print(s.entnehmen(), end="")               # Hauptkategorie ohne Trennzeichen
    while not s.istLeer():
        print(" > " + s.entnehmen(), end="")
    # Ende while
# Ende zeigePfad

Als Struktogramm:

Punkteverteilung:

• Stapel erzeugen, Laufvariable mit id initialisieren: 1 Punkt

• Schleife über die Oberkategorien mit korrekter Bedingung (Hauptkategorie wird noch abgelegt, Schleife endet bei 0): 3 Punkte

• Bezeichnung ablegen: 1 Punkt

• zur Oberkategorie weitergehen: 1 Punkt

• erste Bezeichnung (Hauptkategorie) ohne Trennzeichen ausgeben: 2 Punkte

• Stapel bis zum Ende leeren und mit > ausgeben: 2 Punkte

Alternativen mit voller Punktzahl, wenn korrekt:

• ohne Stapel, den Pfad als Zeichenkette von rechts nach links aufbauen: pfad := bezeichnung[aktuell], dann in der Schleife pfad := bezeichnung[aktuell] & " > " & pfad, am Ende Ausgabe pfad;

• Trennzeichen über einen Merker („erstes Element“) statt der getrennten ersten Ausgabe.

Zum Schutz vor Zyklen (Teilaufgabe ad) kann die erste Schleife zusätzlich einen Zähler mit Obergrenze erhalten; das ist hier nicht verlangt.

• Ein Testfall genügt. (1 Punkt)

• Begründung: Anweisungsüberdeckung verlangt, dass jede Anweisung mindestens einmal ausgeführt wird. Ein Aufruf mit einer Unterkategorie führt in der äußeren Ebene den Rumpf der Verzweigung aus (rekursiver Aufruf, Trennzeichen) und erreicht im innersten Aufruf die Hauptkategorie, bei der die Verzweigung übersprungen wird. Die Ausgabe der Bezeichnung läuft in jeder Ebene. Da hier beide Ausgänge der Verzweigung durchlaufen werden, ist mit demselben Testfall sogar die Zweigüberdeckung erreicht. (1 Punkt)

• Testfall: z. B. id = 8, erwartete Ausgabe Komponenten > Beleuchtung (jede andere Unterkategorie ist ebenso richtig). Eine Hauptkategorie allein (z. B. id = 5) reicht nicht, weil der Rumpf der Verzweigung nicht ausgeführt wird. (1 Punkt)

JANA Pseudo-Pascal Pseudo-Pascal (deutsch) Pseudo-Python all none

int artikelGesamt(int id) {
    int summe = anzahlArtikel(id)                  // Artikel direkt in der Kategorie
    int kinder[] = unterkategorien(id)
    for (int i = 0 … length(kinder)-1) {
        summe = summe + artikelGesamt(kinder[i])   // rekursiv je Unterkategorie
    }
    return summe
}

FUNCTION artikelGesamt(id: integer) : integer
    summe: integer := anzahlArtikel(id)            // Artikel direkt in der Kategorie
    kinder: array of integer := unterkategorien(id)
    for i := 0 to length(kinder) - 1 do
        summe := summe + artikelGesamt(kinder[i])  // rekursiv je Unterkategorie
    end for
    RETURN summe
END artikelGesamt

Funktion artikelGesamt(id: integer): integer
    summe: integer := anzahlArtikel(id)            // Artikel direkt in der Kategorie
    kinder: integer[] := unterkategorien(id)
    zähle i von 0 bis laenge(kinder) - 1
        summe := summe + artikelGesamt(kinder[i])  // rekursiv je Unterkategorie
    Ende zähle
    Rückgabe summe
Ende artikelGesamt

def artikelGesamt(id):
    summe = anzahlArtikel(id)                      # Artikel direkt in der Kategorie
    kinder = unterkategorien(id)
    for i in range(len(kinder)):
        summe = summe + artikelGesamt(kinder[i])   # rekursiv je Unterkategorie
    # Ende for
    return summe
# Ende artikelGesamt

Punkteverteilung:

• Summe mit den direkten Artikeln beginnen: 2 Punkte

• Unterkategorien holen und vollständig durchlaufen (Indexgrenzen): 2 Punkte

• rekursiver Aufruf je Unterkategorie, Ergebnis aufaddieren: 3 Punkte

• Rückgabe der Summe: 1 Punkt

Die Abbruchbedingung steckt in der Schleife: Bei einer Kategorie ohne Unterkategorien läuft die Schleife nicht, es folgt kein weiterer Aufruf. Eine ausdrückliche Abfrage wenn laenge(kinder) = 0 dann Rückgabe anzahlArtikel(id) ist ebenso richtig. Fehler mit Punktabzug: Rückgabewert des rekursiven Aufrufs nicht addiert; Summe als globale Variable, die nicht zurückgesetzt wird; nur die direkten Unterkategorien gezählt.

• Rückgabewert: 8 (Fahrräder 0 + E-Bikes 3 + Lastenräder 0 + E-Lastenräder 2 + Long John 1 + Stadträder 2). (1,5 Punkte)

• Aufrufe: 6 – je einer für die Kategorien 1, 2, 3, 11, 12 und 4 (in dieser Reihenfolge). (1,5 Punkte)

• zeigePfad ruft sich je Ebene höchstens einmal auf (lineare Rekursion): Der Weg führt in einer Linie zur Hauptkategorie; eine Schleife mit einer Laufvariablen genügt. (1 Punkt)

• artikelGesamt ruft sich je Ebene für jede Unterkategorie auf (Baumrekursion). Nach der Rückkehr aus einem Zweig muss das Programm wissen, welche Geschwister-Kategorien noch offen sind – das merkt sich bei der Rekursion der Aufrufstapel. (1 Punkt)

• Eine iterative Fassung braucht deshalb eine eigene Hilfsdatenstruktur für die noch zu besuchenden Kategorien, z. B. einen Stapel (Tiefensuche) oder eine Warteschlange (Breitensuche): Start-ID ablegen, solange nicht leer eine ID entnehmen, ihre Artikel addieren und ihre Unterkategorien ablegen. (1 Punkt)

Ebenfalls richtig: Alle Kategorien des Arrays durchlaufen und für jede über oberId nach oben prüfen, ob id auf ihrem Pfad liegt – ohne Hilfsdatenstruktur, aber mit deutlich mehr Rechenaufwand.

• Die Funktion arbeitet nach dem Verfahren der binären Suche (Intervallhalbierung, Teile und herrsche). (1 Punkt)

• Sie vergleicht den gesuchten Wert mit dem Element in der Mitte des Suchbereichs links … rechts. Bei Gleichheit gibt sie den Index zurück. Ist das mittlere Element kleiner, sucht sie in der rechten Hälfte weiter, sonst in der linken. Ist der Bereich leer (links > rechts), ist der Wert nicht enthalten, Rückgabe −1. (1 Punkt)

• Voraussetzung: Das Array muss aufsteigend sortiert sein. (1 Punkt)

Rückgabewerte: Suche nach 189 → 7; Suche nach 120 → −1 (Schleife endet, weil links > rechts).

Bewertung: Suche nach 189 2 Punkte (je Durchlauf 0,5, Rückgabe 1), Suche nach 120 3 Punkte (je Durchlauf 0,5, Endzustand 0,5, Rückgabe 1).

JANA Pseudo-Pascal Pseudo-Pascal (deutsch) Pseudo-Python all none

int sucheRekursiv(int ids[], int wert, int links, int rechts) {
    if (links > rechts) {                          // Suchbereich leer
        return -1
    }
    int mitte = (links + rechts) / 2
    if (ids[mitte] == wert) {
        return mitte
    }
    if (ids[mitte] < wert) {
        return sucheRekursiv(ids, wert, mitte + 1, rechts)
    } else {
        return sucheRekursiv(ids, wert, links, mitte - 1)
    }
}

// Erstaufruf
int index = sucheRekursiv(ids, wert, 0, length(ids) - 1)

FUNCTION sucheRekursiv(ids: array of integer, wert: integer, links: integer, rechts: integer) : integer
    if (links > rechts) then                       // Suchbereich leer
        RETURN -1
    end if
    mitte: integer := (links + rechts) div 2
    if (ids[mitte] = wert) then
        RETURN mitte
    end if
    if (ids[mitte] < wert) then
        RETURN sucheRekursiv(ids, wert, mitte + 1, rechts)
    else
        RETURN sucheRekursiv(ids, wert, links, mitte - 1)
    end if
END sucheRekursiv

// Erstaufruf
index: integer := sucheRekursiv(ids, wert, 0, length(ids) - 1)

Funktion sucheRekursiv(ids: integer[], wert: integer, links: integer, rechts: integer): integer
    wenn links > rechts dann                       // Suchbereich leer
        Rückgabe -1
    Ende wenn
    mitte: integer := (links + rechts) div 2
    wenn ids[mitte] = wert dann
        Rückgabe mitte
    Ende wenn
    wenn ids[mitte] < wert dann
        Rückgabe sucheRekursiv(ids, wert, mitte + 1, rechts)
    sonst
        Rückgabe sucheRekursiv(ids, wert, links, mitte - 1)
    Ende wenn
Ende sucheRekursiv

// Erstaufruf
index: integer := sucheRekursiv(ids, wert, 0, laenge(ids) - 1)

def sucheRekursiv(ids, wert, links, rechts):
    if links > rechts:                             # Suchbereich leer
        return -1
    # Ende if
    mitte = (links + rechts) // 2
    if ids[mitte] == wert:
        return mitte
    # Ende if
    if ids[mitte] < wert:
        return sucheRekursiv(ids, wert, mitte + 1, rechts)
    else:
        return sucheRekursiv(ids, wert, links, mitte - 1)
    # Ende if
# Ende sucheRekursiv

# Erstaufruf
index = sucheRekursiv(ids, wert, 0, len(ids) - 1)

Punkteverteilung:

• Abbruchbedingung „Bereich leer“ vor dem Zugriff auf ids[mitte], Rückgabe −1: 2 Punkte

• Mitte berechnen, Treffer zurückgeben: 1 Punkt

• rekursiver Aufruf für die rechte Hälfte mit mitte + 1: 1,5 Punkte

• rekursiver Aufruf für die linke Hälfte mit mitte - 1: 1,5 Punkte

• Ergebnis der rekursiven Aufrufe jeweils zurückgeben: 1 Punkt

• Erstaufruf mit 0 und laenge(ids) - 1: 1 Punkt

Die Laufvariablen links und rechts der Schleife sind zu Parametern geworden; die negierte Schleifenbedingung (links > rechts) ist die Abbruchbedingung.

Fehler 1 – Rückgabewert geht verloren (3 Punkte): Der rekursive Aufruf in Zeile 10 liefert ein Ergebnis, das nicht zurückgegeben wird. Die Funktion endet in diesem Zweig ohne Rückgabewert. Beispiel 189: sucheR(0, 9) → Mitte 4 (151 < 189) → Zeile 10 ruft sucheR(4, 9) auf → … → ein innerer Aufruf findet 189 an Index 7, aber der Wert wird von den äußeren Ebenen verworfen; der Erstaufruf liefert keinen (bzw. einen undefinierten) Wert. In Java meldet der Compiler missing return statement. Korrektur: Rückgabe sucheR(ids, wert, mitte + 1, rechts).

Fehler 2 – Bereich wird nicht kleiner (3 Punkte): Für die rechte Hälfte wird mitte statt mitte + 1 als neue linke Grenze übergeben. Ist links = mitte (das passiert, sobald der Bereich nur noch ein oder zwei Elemente umfasst), wird die Funktion immer wieder mit denselben Grenzen aufgerufen: Endlosrekursion und Stapelüberlauf. Beispiel 120: sucheR(0, 9) → sucheR(0, 3) → Mitte 1 (117 < 120) → sucheR(1, 3) → Mitte 2 (123 > 120) → sucheR(1, 1) → Mitte 1 (117 < 120) → sucheR(1, 1) → … Beispiel 215: ab sucheR(8, 9) mit Mitte 8 endlos. Korrektur: mitte + 1 übergeben (siehe oben).

• Ja: Die Abbruchprüfung links > rechts steht nach dem Zugriff auf ids[mitte]. (1 Punkt)

• Bei einem leeren Array (z. B. wenn die Anmeldedaten am Vorabend nicht übertragen wurden) ist links = 0 und rechts = -1; mitte ist dann 0 oder −1 (je nach Rundung der ganzzahligen Division). Der Zugriff liegt außerhalb des Arrays, es kommt zum Laufzeitfehler (ArrayIndexOutOfBoundsException). (1 Punkt)

• Bei einem nicht leeren Array liefert die Reihenfolge kein falsches Ergebnis, wenn die ganzzahlige Division wie in Java zur Null hin rundet: Ist der Bereich leer geworden (links = rechts + 1), zeigt mitte auf ein Element unmittelbar neben dem Suchbereich, das wegen der Sortierung nicht gleich wert sein kann. Rundet div ab (z. B. // in Python), entsteht beim Bereich 0 … -1 der Index −1. Sauber ist nur, die Abbruchbedingung vor dem ersten Zugriff zu prüfen. (1 Punkt)

Geg.: n = 400 Anmeldungen; s = 96\ \mathrm{B} je Aufruf; S = 256\ \mathrm{KiB} = 262.144\ \mathrm{B}

Ges.: höchste Zahl der Vergleiche k, Aufruftiefe t, Stapelbedarf M

Mit k Vergleichen lassen sich höchstens 2^k - 1 Elemente durchsuchen (jeder Vergleich halbiert den Rest). Gesucht ist das kleinste k mit

2^k - 1 \geq n \quad | + 1

2^k \geq n + 1 \quad | \log_2

k \geq \log_2(n + 1) = \log_2(401) \approx 8{,}647

\underline{\underline{k = 9}} \text{ Vergleiche (ganzzahlig aufgerundet)}

Die rekursive Fassung braucht im ungünstigsten Fall (Wert nicht enthalten) neben den 9 Aufrufen mit Vergleich einen letzten Aufruf, der links > rechts feststellt:

t = k + 1 = 9 + 1 = \underline{\underline{10}} \text{ Aufrufe}

M = t \cdot s = 10 \cdot 96\ \mathrm{B} = \underline{\underline{960\ \mathrm{B}}}

Das sind weniger als 0,4 % des Stapelspeichers. Bewertung: je Ergebnis 1 Punkt; t = 9 und M = 864\ \mathrm{B} mit nachvollziehbarer Begründung ebenfalls richtig.

Ges.: kleinste Anzahl n, bei der (n + 1) \cdot s > S

(n + 1) \cdot s > S \quad | : s

n + 1 > \frac{S}{s} \quad | - 1

n > \frac{S}{s} - 1 = \frac{262.144\ \mathrm{B}}{96\ \mathrm{B}} - 1 = \frac{8.189}{3} \approx 2.729{,}667

\underline{\underline{n = 2.730}} \text{ Anmeldungen}

Probe: 2.731 \cdot 96\ \mathrm{B} = 262.176\ \mathrm{B} > 262.144\ \mathrm{B}, bei 2.729 Anmeldungen sind es 262.080\ \mathrm{B}. Für das Barcamp mit 400 Anmeldungen (38.496 B) reicht der Speicher noch, für größere Veranstaltungen nicht – und andere Daten auf dem Stapel senken die Grenze weiter.

Bewertung: Ansatz 1 Punkt, Umformung 1 Punkt, Ergebnis 1 Punkt.

• Eine Funktion ist endrekursiv, wenn der rekursive Aufruf die letzte Aktion ist und sein Ergebnis unverändert zurückgegeben wird. (1 Punkt)

• sucheRekursiv ist endrekursiv: In beiden Zweigen steht Rückgabe sucheRekursiv(…), danach ist nichts mehr zu tun. (1 Punkt)

• artikelGesamt ist nicht endrekursiv: Nach jedem rekursiven Aufruf wird das Ergebnis noch zur Summe addiert und die Schleife fortgesetzt; der Stapelrahmen wird weiter gebraucht. (1 Punkt)

• Compiler mit Endrekursions-Optimierung ersetzen den Aufruf durch einen Sprung, sodass kein neuer Stapelrahmen entsteht (konstanter Speicher). Java bzw. die JVM führen diese Optimierung nicht durch; in Java spart die endrekursive Form also keinen Stapelspeicher. (1 Punkt)

Beispiel für eine begründete Stellungnahme (je ein Punkt für ein zutreffendes Argument, ein Punkt für ein begründetes Fazit):

• Für die binäre Suche ist das Risiko eines Stapelüberlaufs praktisch ausgeschlossen: Die Aufruftiefe wächst nur logarithmisch (10 Aufrufe bei 400 Anmeldungen, 21 bei einer Million). Ein „nur“ ist daher übertrieben.

• Die iterative Fassung ist trotzdem etwas schneller (keine Aufrufe), braucht konstanten Speicher und ist ebenso kurz und gut lesbar; sie bietet beim Check-in also keinen Nachteil.

• Fazit: Ich stimme Svenja im Ergebnis zu – auf dem Terminal sollte die iterative Fassung laufen, weil sie robust und nicht schwerer verständlich ist. Die rekursive Fassung wäre aber ebenfalls vertretbar; ausgeschlossen werden muss nur eine Rekursion, deren Tiefe mit der Datenmenge linear wächst (siehe db).

Eine andere Position mit stimmiger Begründung ist ebenfalls richtig.

JANA Pseudo-Pascal Pseudo-Pascal (deutsch) Pseudo-Python all none

zeigeBelegung(int muster, int stellen) {
    if (stellen > 0) {
        zeigeBelegung(muster / 2, stellen - 1)     // erst die Slots weiter links
        write(muster % 2)                          // dann das eigene Bit
    }
}

PROCEDURE zeigeBelegung(muster: integer, stellen: integer)
    if (stellen > 0) then
        zeigeBelegung(muster div 2, stellen - 1)   // erst die Slots weiter links
        write(muster mod 2)                        // dann das eigene Bit
    end if
END zeigeBelegung

Prozedur zeigeBelegung(muster: integer, stellen: integer)
    wenn stellen > 0 dann
        zeigeBelegung(muster div 2, stellen - 1)   // erst die Slots weiter links
        Ausgabe muster mod 2                       // dann das eigene Bit
    Ende wenn
Ende zeigeBelegung

def zeigeBelegung(muster, stellen):
    if stellen > 0:
        zeigeBelegung(muster // 2, stellen - 1)    # erst die Slots weiter links
        print(muster % 2, end="")                  # dann das eigene Bit
    # Ende if
# Ende zeigeBelegung

Punkteverteilung:

• Abbruchbedingung über stellen (bei 0 nichts mehr ausgeben): 1 Punkt

• rekursiver Aufruf mit muster div 2 und stellen - 1 (Problem wird kleiner): 2 Punkte

• Ausgabe von muster mod 2 nach dem rekursiven Aufruf, damit Slot 1 links steht: 2 Punkte

Weil die Abbruchbedingung an stellen und nicht an muster > 0 hängt, entstehen die führenden Nullen von selbst. Steht die Ausgabe vor dem Aufruf, erscheint das Muster spiegelverkehrt (Slot 5 links): höchstens 3 Punkte.

Ausgabe: 01101 (1 Punkt). Belegt sind die Slots 2, 3 und 5 (8 + 4 + 1 = 13) (1 Punkt).