Aufgabe "Rekursion"
← Funktionen | ● | Zeiger →
a) Berechnen Sie die Logarithmusfunktion zur Basis 2 rekursiv. Die Logarithmusfunktion ist für die natürlichen Zahlen (positive Ganzzahlen) wie folgt definiert:
$ log_2(x)=log_2(\frac{x}{2})+1 $
Beispiel:
$ log_2(10) + 1 = $
$ log_2(5) + 1 + 1 = $
$ log_2(2) + 1 + 1 + 1 = $
$ log_2(1) + 1 + 1 + 1 + 1 = 4 $
Protokollieren Sie am Anfang der Funktion den Funktionsparameter und am Ende der Funktion den Rückgabewert mit printf(). Was ist die Reihenfolge der Ausgabe der Rückgabewerte?
b) Berechnen Sie die Multiplikation von zwei positiven Ganzzahlen rekursiv nur mit Hilfe der Addition.
$ mul(0,y)=0 $
$ mul(x,y)=mul(x-1, y)+y $
c) Berechnen Sie die schnelle Multiplikation von zwei positiven Ganzzahlen rekursiv nur mit Hilfe der Addition und binärem Shift (als Ersatz für *2 bzw. /2).
$ mul(0,y)=0 $
$ mul(x,y)= \left\{ \begin{array}{r r l} x & ungerade: & mul(x-1, y)+y \\ x & gerade: & 2 \cdot mul(\frac{x}{2}, y) \end{array} \right. $
Welche Variante der Multiplikation ist schneller? Protokollieren sie dazu die Anzahl der Aufrufe mit Hilfe einer globalen Zählvariable. Welches Laufzeitverhalten tritt auf: konstant, logarithmisch, linear, quadratisch (d.h. was ist die Anzahl der Funktionsaufrufe für ein bestimmtes x und y, zum Beispiel für x=1000,y=42) ?
d) Schreiben Sie eine rekursive Funktion, welche die Quersumme einer Ganzzahl berechnet.
Zusatzaufgabe:
e) Schreiben Sie eine rekursive Funktion, welche eine Ganzzahl in Hexadezimaldarstellung ausgibt. Geben Sie am Anfang den Prefix “0x” mit aus. Fügen Sie zwecks besserer Lesbarkeit nach jeweils vier Ziffern einen Unterstrich ein.
← Funktionen | ● | Zeiger →