Rekursionen

Manche Aufgaben lassen sich auf eine einfachere Version ihrer selbst zurückführen. Dies bedeutet, dass man die Aufgabe so lange auf sich selbst zurückführt, bis sie sich einfach lösen lässt. Ein solches Verfahren nennt man Rekursion.

1. Schreiben Sie ein Programm zur rekursiven Berechnung der Fakultät einer natürlichen Zahl n!
2. Die Berechnung der Fakultät lässt sich auch auf eine andere Art lösen. Man kann nämlich n! dadurch berechnen, dass man zunächst 1 mit 2 multipliziert, dann dieses Ergebnis mit 3, dieses Ergebnis dann mit 4 usw., bis man schließlich n erreicht hat. Ein solches Vorgehen heißt Iteration und ist uns bereits aus dem Kapitel zyklische Strukturen vertraut. Schreiben Sie ein Programm, welches die Fakultät iterativ berechnet!
3. Berechnen Sie die Summe der ersten n natürlichen Zahlen s(n) = 1 + 2 + 3 + ... + n rekursiv. Orientieren Sie sich dabei an dem rekursiven Ansatz der Fakultätsfunktion!
4. Berechnen Sie die Summe der ersten n Quadratzahlen q_summe(n) = 1² + 2² + ... + n² mit Hilfe einer rekursiven Funktion!

5. Von Leonardo Pisano (ca. 1170 bis 1230), auch Fibonacci genannt, stammt folgende Aufgabe: In einer von Kaninchen freien Gegend wird ein frisch geborenes Pärchen Kaninchen ausgesetzt. Nach einem Monat ist es geschlechtsreif. Nach zwei Monaten bringe dieses Pärchen wieder ein Pärchen zur Welt. Nach drei Monaten sind dann drei Pärchen vorhanden: Das zuerst ausgesetzte hat wieder ein Pärchen geboren, während das zum Zeitpunkt 2 (Monate) geborene Pärchen geschlechtsreif geworden ist. Da kein Pärchen sterben soll, sind also nach vier Monaten 5 Pärchen vorhanden (siehe Abbildung).

   

   n (Monate)	0	1	2	3	4	5	6	7	8	9
   Anzahl der Pärchen	1	1	2	3	5	8	?	?	?	?

1. Füllen Sie die Tabelle vollständig aus!

2. Bestätigen Sie, dass gilt:

   

   wobei A(n) die Anzahl der Pärchen von Kaninchen in n Monaten ist.

3. Schreiben Sie ein Programm, das nach Eingabe von n den Bestand an Kaninchenpaaren ausgibt!
4. Schreiben Sie ein Programm, das nach Eingabe einer Kaninchenzahl (in Pärchen) ausgibt, wann diese Zahl erreicht oder überschritten ist!
entnommen aus: Junger u.a.: Informatik, Diesterweg/Sauerländer, 1988