====== LU01.A12 - Trace Table für die Collatz-Folge ======

<WRAP center round todo 60%>
Erstellen Sie einen Trace Table für einen Algorithmus mit ''while''-Schleife, bei dem sich der Parameter selbst laufend verändert – und vergleichen Sie ihn mit der rekursiven Fassung desselben Algorithmus.
</WRAP>

===== Erklärung der Collatz-Folge =====

Die Collatz-Folge (auch //(3n+1)-Problem//) folgt einer verblüffend einfachen Regel. Man startet mit einer positiven ganzen Zahl und wiederholt:

  * Ist die Zahl **gerade**, halbiere sie.
  * Ist die Zahl **ungerade**, multipliziere sie mit 3 und addiere 1.

Man hört auf, sobald die Zahl 1 erreicht ist. Ob das für //jede// Startzahl passiert, ist bis heute unbewiesen – ausprobieren kann man es trotzdem.

===== Algorithmus =====

<code python>
def collatz(n):
    schritte = 0
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
        schritte += 1
    return schritte


if __name__ == '__main__':
    start = 6
    print(f'Von {start} bis 1 sind es {collatz(start)} Schritte.')
</code>

===== Aufgabe =====

  * Analysieren Sie den Code Schritt für Schritt für den Startwert ''n = 6''.
  * Erstellen Sie einen Trace Table mit dem Wert von ''n'' **vor** und **nach** dem Schritt, dem Ergebnis der Bedingung und dem Zählerstand.
  * Verwenden Sie die folgende Struktur:

^ Schritt ^ n (vorher) ^ n % 2 == 0 ^ angewandte Regel ^ n (nachher) ^ schritte ^
| 1 | 6 | Ja | n // 2 | 3 | 1 |
| 2 | | | | | |

  * Führen Sie die Tabelle fort, bis die Schleifenbedingung ''n != 1'' nicht mehr erfüllt ist.

==== Beispielinput ====

<code python>
start = 6
</code>

==== Beispieloutput ====

<code>
Von 6 bis 1 sind es 8 Schritte.
</code>

===== Teil 2: Dieselbe Berechnung ohne veränderliche Variablen =====

Die folgende Fassung berechnet dasselbe, verändert aber keine einzige Variable. Der Zustand wandert stattdessen durch die Parameter der rekursiven Aufrufe.

<code python>
def collatz_rekursiv(n, schritte=0):
    if n == 1:
        return schritte
    if n % 2 == 0:
        return collatz_rekursiv(n // 2, schritte + 1)
    return collatz_rekursiv(3 * n + 1, schritte + 1)
</code>

Erstellen Sie auch dafür einen Trace Table:

^ Aufruf ^ n ^ schritte ^ nächster Aufruf ^ Rückgabewert ^
| 1 | 6 | 0 | collatz_rekursiv(3, 1) | |
| 2 | | | | |

<WRAP center round tip 80%>
**Hinweis zur Rückgabespalte**

Füllen Sie die Spalte //Rückgabewert// erst von unten nach oben aus. Der innerste Aufruf liefert seinen Wert zurück, und dieser Wert wird von jedem darüberliegenden Aufruf unverändert weitergereicht.
</WRAP>

===== Auswertungsfragen =====

  - Welche Spalten des ersten Trace Tables werden im zweiten überflüssig? Was sagt das über den Unterschied zwischen veränderlichem Zustand und Parameterübergabe aus?
  - Im ersten Algorithmus bezeichnet ''n'' nacheinander acht verschiedene Zahlen. Im zweiten hat jedes ''n'' innerhalb seines Aufrufs genau einen Wert und behält ihn. Warum ist die zweite Variante leichter nachzuvollziehen?
  - Was passiert bei ''collatz(0)''? Erklären Sie, warum – und welche der beiden Fassungen den Fehler früher sichtbar macht.
  - Prüfen Sie Ihre Tabelle mit dem Startwert ''n = 7''. Wie viele Schritte sind es? Warum braucht eine so kleine Zahl so viele Schritte?

===== Abgabe =====

Geben Sie beide ausgefüllten Trace Tables und die beantworteten Auswertungsfragen in Moodle ab.

----
{{tag>M323-LU01 M323-C1B M323-A1I}}
[[https://creativecommons.org/licenses/by-nc-sa/4.0/ch/|{{https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png}}]] (c) Kevin Maurizi