Rekursion und rekursive Funktionen

Herkunft des Begriffes

Mona Lisa Fraktal Die Rekursion hat etwas mit Unendlichkeit zu tun. Ich weiß, dass die Rekursion etwas mit Unendlichkeit zu tun hat. Er denkt, dass ich weiß, dass die Rekursion etwas mit Unendlichkeit zu tun hat. Sie ist sicher, dass er denkt, dass ich weiß, dass die Rekursion etwas mit Unendlichkeit zu tun hat. Wir glauben nicht, dass sie sicher ist, dass er denkt, dass ich weiß, dass die Rekursion etwas mit Unendlichkeit zu tun hat. ... Dieses sprachliche Spiel könnten wir beliebig fortsetzen. Dies ist ein Beipiel für eine Art von Rekursion in der natürlichen Sprache. Die Rekursion ist nicht nur eine fundamentale Eigenschaft der natürlichen Sprache, sondern der menschlichen kognitiven Fähigkeiten. Unser ganzes Denken basiert auf rekursiven Denkprozessen. Der Linguist Noam Chomsky hatte einen Formalismus eingeführt, um sprachliche Ausdrücke mit Hilfe einer Metasprache formal zu definieren. Diese Definition definiert rekursiv eine Grammatik. Diese formalen Sprachen von Chomsky werden auch zur Definition und Spezifikation von Programmiersprachen in der Informatik benutzt. Die Beweismethode der Vollständigen Induktion in der Mathematik ist auch eine Art von Rekursion.

Das Adjektiv "rekursiv" stammt vom lateinischen Verb "recurrere", was "zurücklaufen" bedeutet. Das ist genau das, was eine rekursive Definition oder eine rekursive Funktion macht: Sie läuft gewissermaßen zurück auf sich selbst, indem sie sich selbst aufruft. Jedem, der sich bereits ein wenig mit Mathematik oder Informatik beschäftigt hat, dürfte wohl die Fakultät begegnet sein. Vor allem, wenn man bereits eine Programmiersprache erlernt hat. Die Fakultätsfunktion ist das Standardbeispiel für die Einführung der Rekursion in nahezu jedem Tutorial. Die Gründe liegen auf der Hand: Der mathematische Hintergrund ist leicht zu verstehen und sie lässt sich besonders leicht rekursiv programmieren. Also folgen wir der Tradition und widmen uns auch in unserem Python-Tutorial dieser Funktion. Mathematisch wird die Fakultät wie folgt definiert:

n! = n * (n-1)!, if n > 1 and f(1) = 1

Definition der Rekursion

Die Rekursion ist eine Programmiertechnik oder Programmierkonzept, indem eine Funktion sich selbst ein oder mehrmals in ihrem Funktionskörper (body) aufruft. Eine Funktionsdefinition, die die Bedingungen der Rekursion erfüllt, nennen wir eine rekursive Funktion.

Abbruchbedingung:
Eine rekursive Funktion muss terminieren, damit man sie in einem Programm benutzen kann. Eine rekursive Funktion terminiert, wenn mit jedem Rekursionsschritt das Problem reduziert wird - man könnte auch sagen vereinfacht wird - und sich "in Richtung" der Abbruchbedingung bewegt, d.h. dem Fall, in dem die Funktion sich nicht mehr selbst aufruft. So liefert beispielweise die Fakultätsfunktion für das Argument 1 den Wert 1 zurück, ohne dass zur Berechnung ein weiterer rekursiver Aufruf notwendig ist. (Anmerkung für Mathematiker: Das Abbruchkriterium in einer rekursiven Funktion entspricht der Induktionsverankerung bei der vollständigen Induktion!)
Eine rekursive Funktion kann in eine Endlosschleife führen, wenn das Abbruchkriterium nicht erreicht wird.

Beispiel für die Fakultät:

4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1


Ersetzt man die ausgerechneten Werte in der jeweiligen Ursprungsgleichung, erhält man für 4! folgenden Ausdruck:

4! = 4 * 3 * 2 * 1

Ganz allgemein könnten wir sagen: Rekursion ist eine Methode in der Informatik, in der die Lösung für ein Problem auf die Lösung kleinerer Instanzen des Problems zurückgeführt wird.

Rekursive Funktionen in Python

Als Beispiel für eine rekursive Funktion in Python wählen wir, wie bereits anfangs angedeutet, eine rekursive Implementierung der Fakultätsfunktion. Man sieht, dass das Pythonskript ebenso elegant wie die mathematische Funktion ist:
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)
Wenn wir nachvollziehen wollen, wie die Funktion funktioniert, können wir zwei print()-Funktionen ergänzen:
def factorial(n):
    print("factorial has been called with n = " + str(n))
    if n == 1:
        return 1
    else:
        res = n * factorial(n-1)
        print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res)
        return res	

print(factorial(5))
Obiges Python-Skript liefert folgende Ausgaben:
factorial has been called with n = 5
factorial has been called with n = 4
factorial has been called with n = 3
factorial has been called with n = 2
factorial has been called with n = 1
intermediate result for  2  * factorial( 1 ):  2
intermediate result for  3  * factorial( 2 ):  6
intermediate result for  4  * factorial( 3 ):  24
intermediate result for  5  * factorial( 4 ):  120
120
Die Fakultätsfunktion lässt sich natürlich auch iterativ schreiben:
def iterative_factorial(n):
    result = 1
    for i in range(2,n+1):
        result *= i
    return result

Die Tücken der Rekursion

Fibonacci Squares In diesem Unterkapitel von unserem Tutorial geht es um ein spezielles Problem bei der Rekursion. Ruft eine Funktion sich in einem Ausdruck wiederholt auf, erhalten wir ein exponentielles Laufzeitverhalten. Am Beispiel der Fibonacci-Zahlen demonstrieren wir, wie dieses exponentielle Laufzeitverhalten zustande kommt.

Die Fibonacci-Zahlen sind eine unendliche Zahlenfolge. Deshalb werden die Fibonacci-Zahlen auch als Fibonacci-Folge bezeichnet.

Aufgabe:
Im folgenden sehen sie die ersten Glieder der Fibonacci-Folge. Versuchen sie doch einmal das Konstruktionsprinzip dieser Folge zu erkennen:

0,1,1,2,3,5,8,13,21,34,55,89, ...

Es sollte hoffentlich nicht zu schwer gewesen sein. Jede Zahl, außer den beiden ersten, ergibt sich aus der Summe der beiden Vorgänger.

Formale Definition der Fibonacci-Zahlen:
Fn = Fn-1 + Fn-2
with F0 = 0 and F1 = 1

Die Fibonacci-Zahlen sind nach dem Mathematiker Leonardo von Pisa, besser bekannt als Fibonacci, benannt. In seinem Buch "Liber Abaci", das im Jahre 1202 veröffentlicht wurde, führte er diese Folge als Übungsaufgabe ein. In dieser Übung geht es um Kaninchen. Seine Folge beginnt mit F1 = 1, während in modernen Mathematikbüchern und Büchern über Programmiersprachen die Folge meistens mit dem Wert für das Argument 0 startet, also F0 = 0. Dies ist aber gewissermaßen nur Geschmackssache, denn ob man bei 0 oder 1 startet hat keine Auswirkungen auf die weiteren Folgeglieder.

Die Fibonacci-Zahlen resultieren also aus einem "künstlichen" Kaninchenproblem, das die folgenden Bedingungen erfüllt:
Die Fibonacci-Zahlen geben also die Anzahl der Paare am Ende eines bestimmten Monates an.

Fibonacci Folge in Python

Nun kommen wir endlich wieder zu Python und den rekursiven Funktionen zurück. Die Fibonacci-Zahlen lassen sich sehr leicht als rekursive Python-Funktion realisieren. Diese spiegelt ziemlich exakt die rekursive mathematische Funktion wieder:
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
Eine iterative Funktion zur Berechnung der Fibonacci Zahlen lässt sich ebenso leicht in Python bewerkstelligen, wie wir im folgenden Skript sehen können:
def fibi(n):
    old, new = 0, 1
    if n == 0:
        return 0
    for i in range(n-1):
        old, new = new, old + new
    return new
Benutzt man die beiden Funktionen fib() und fibi() stellt man sehr schnell fest, dass sie ein deutlich unterschiedliches Laufzeitverhalten an den Tag legen. Bei kleinen Werten z.B. n = 10, 11 oder 15 hat man rein gefühlsmäßig, also ohne exakte Zeitmessung das Gefühl, dass fibi() und fib() genauso schnell wären. Aber gibt man beispielsweise den Wert 30 für n an, zeigt sich ein deutlich anderes Laufzeitverhalten. fib() braucht nun sekundenlang, während fibi() weiterhin "sofort" mit dem Ergebnis da ist. Um dieses Gefühl mit soliden Messwerten zu untermauern, haben wir ein Skript geschrieben, mit dem wir die Zeiten messen können. Zunächst speichern wir die beiden obigen Funktionen in einer Datei fibonacci.py, die wir dann in unten stehendem Programm (fibonacci_laufzeit.py) als Modul einlesen können:

from timeit import Timer

t1 = Timer("fib(10)","from fibonacci import fib")

for i in range(1,41):
	s = "fib(" + str(i) + ")"
	t1 = Timer(s,"from fibonacci import fib")
	time1 = t1.timeit(3)
	s = "fibi(" + str(i) + ")"
	t2 = Timer(s,"from fibonacci import fibi")
	time2 = t2.timeit(3)
	print("n=%2d, fib: %8.6f, fibi:  %7.6f, percent: %10.2f" % (i, time1, time2, time1/time2))
time1 ist die Zeit in Sekunden, die drei Aufrufe von fib(n) benötigen und time2 ist entsprechend die Zeit für drei Aufrufe der iterativen Funktion fibi(). Wenn wir uns die Ergebnisse anschauen, sehen wir, dass fib(20) etwa 14 Millisekunden benötigt, während fibi(20) für drei Aufrufe gerade 0,011 Millisekunden benötigt. fib(20) ist also etwa 1300 Mal schneller als fib(20).
fib(40) braucht bereits 215 Sekunden, also mehr als 3,5 Minuten, während fibi(4) sich mit 0,016 Millisekunden begnügt.

n= 1, fib: 0.000004, fibi:  0.000005, percent:       0.81
n= 2, fib: 0.000005, fibi:  0.000005, percent:       1.00
n= 3, fib: 0.000006, fibi:  0.000006, percent:       1.00
n= 4, fib: 0.000008, fibi:  0.000005, percent:       1.62
n= 5, fib: 0.000013, fibi:  0.000006, percent:       2.20
n= 6, fib: 0.000020, fibi:  0.000006, percent:       3.36
n= 7, fib: 0.000030, fibi:  0.000006, percent:       5.04
n= 8, fib: 0.000047, fibi:  0.000008, percent:       5.79
n= 9, fib: 0.000075, fibi:  0.000007, percent:      10.50
n=10, fib: 0.000118, fibi:  0.000007, percent:      16.50
n=11, fib: 0.000198, fibi:  0.000007, percent:      27.70
n=12, fib: 0.000287, fibi:  0.000007, percent:      41.52
n=13, fib: 0.000480, fibi:  0.000007, percent:      69.45
n=14, fib: 0.000780, fibi:  0.000007, percent:     112.83
n=15, fib: 0.001279, fibi:  0.000008, percent:     162.55
n=16, fib: 0.002059, fibi:  0.000009, percent:     233.41
n=17, fib: 0.003439, fibi:  0.000011, percent:     313.59
n=18, fib: 0.005794, fibi:  0.000012, percent:     486.04
n=19, fib: 0.009219, fibi:  0.000011, percent:     840.59
n=20, fib: 0.014366, fibi:  0.000011, percent:    1309.89
n=21, fib: 0.023137, fibi:  0.000013, percent:    1764.42
n=22, fib: 0.036963, fibi:  0.000013, percent:    2818.80
n=23, fib: 0.060626, fibi:  0.000012, percent:    4985.96
n=24, fib: 0.097643, fibi:  0.000013, percent:    7584.17
n=25, fib: 0.157224, fibi:  0.000013, percent:   11989.91
n=26, fib: 0.253764, fibi:  0.000013, percent:   19352.05
n=27, fib: 0.411353, fibi:  0.000012, percent:   34506.80
n=28, fib: 0.673918, fibi:  0.000014, percent:   47908.76
n=29, fib: 1.086484, fibi:  0.000015, percent:   72334.03
n=30, fib: 1.742688, fibi:  0.000014, percent:  123887.51
n=31, fib: 2.861763, fibi:  0.000014, percent:  203442.44
n=32, fib: 4.648224, fibi:  0.000015, percent:  309461.33
n=33, fib: 7.339578, fibi:  0.000014, percent:  521769.86
n=34, fib: 11.980462, fibi:  0.000014, percent:  851689.83
n=35, fib: 19.426206, fibi:  0.000016, percent: 1216110.64
n=36, fib: 30.840097, fibi:  0.000015, percent: 2053218.13
n=37, fib: 50.519086, fibi:  0.000016, percent: 3116064.78
n=38, fib: 81.822418, fibi:  0.000015, percent: 5447430.08
n=39, fib: 132.030006, fibi:  0.000018, percent: 7383653.09
n=40, fib: 215.091484, fibi:  0.000016, percent: 13465060.78

Was ist faul an unserer rekursiven Implementierung?

Schauen wir uns den Berechnungsbaum an, d.h. die Reihenfolge, in der die Funktionaufrufe erfolgen. Statt fib() schreiben wir allerdings vereinfachend f():

fib() Berechnungsbaum

Wir können sehen, dass der Unterbaum zur Berechnung von f(2) (also fib(2)) drei Mal auftaucht und der Unterbaum zur Berechnung von f(3) zweimal. Wenn man sich vorstellt, f(6) zu berechnen, erkennt man, dass f(4) zweimal aufgerufen wird, f(3) dreimal und so weiter. Das bedeutet, dass alle Berechnungen immer wieder durchgeführt werden, da bereits berechnete Werte nicht gespeichert werden. Sie müssen also immer wieder aufs Neue berechnet werden.

Wir können eine "Erinnerung" für unsere rekursive Version implementieren. Dazu nutzen wir ein Dictionary, in dem wir bereits berechnete Werte speichern:
memo = {0:0, 1:1}
def fibm(n):
    if not n in memo:
        memo[n] = fibm(n-1) + fibm(n-2)
    return memo[n]
Wir schauen uns wieder die benötigten Zeiten im Vergleich zu fibi() an. Dazu benötigen wir wieder das Modul fibonacci.py, welches wir dann in unten stehendem Programm (fibonacci_laufzeit_memorize.py)
from timeit import Timer

t1 = Timer("fib(10)","from fibonacci import fib")

for i in range(1,41):
	s = "fibm(" + str(i) + ")"
	t1 = Timer(s,"from fibonacci import fibm")
	time1 = t1.timeit(3)
	s = "fibi(" + str(i) + ")"
	t2 = Timer(s,"from fibonacci import fibi")
	time2 = t2.timeit(3)
	print("n=%2d, fib: %8.6f, fibi:  %7.6f, percent: %10.2f" % (i, time1, time2, time1/time2))

Wir können sehen, dass unsere neue Funktionsversion sogar schneller ist als die iterative. Insbesondere die großen Argumente haben einen besonderen Vorteil von der Memoisation:
n= 1, fib: 0.000011, fibi:  0.000015, percent:       0.73
n= 2, fib: 0.000011, fibi:  0.000013, percent:       0.85
n= 3, fib: 0.000012, fibi:  0.000014, percent:       0.86
n= 4, fib: 0.000012, fibi:  0.000015, percent:       0.79
n= 5, fib: 0.000012, fibi:  0.000016, percent:       0.75
n= 6, fib: 0.000011, fibi:  0.000017, percent:       0.65
n= 7, fib: 0.000012, fibi:  0.000017, percent:       0.72
n= 8, fib: 0.000011, fibi:  0.000018, percent:       0.61
n= 9, fib: 0.000011, fibi:  0.000018, percent:       0.61
n=10, fib: 0.000010, fibi:  0.000020, percent:       0.50
n=11, fib: 0.000011, fibi:  0.000020, percent:       0.55
n=12, fib: 0.000004, fibi:  0.000007, percent:       0.59
n=13, fib: 0.000004, fibi:  0.000007, percent:       0.57
n=14, fib: 0.000004, fibi:  0.000008, percent:       0.52
n=15, fib: 0.000004, fibi:  0.000008, percent:       0.50
n=16, fib: 0.000003, fibi:  0.000008, percent:       0.39
n=17, fib: 0.000004, fibi:  0.000009, percent:       0.45
n=18, fib: 0.000004, fibi:  0.000009, percent:       0.45
n=19, fib: 0.000004, fibi:  0.000009, percent:       0.45
n=20, fib: 0.000003, fibi:  0.000010, percent:       0.29
n=21, fib: 0.000004, fibi:  0.000009, percent:       0.45
n=22, fib: 0.000004, fibi:  0.000010, percent:       0.40
n=23, fib: 0.000004, fibi:  0.000010, percent:       0.40
n=24, fib: 0.000004, fibi:  0.000011, percent:       0.35
n=25, fib: 0.000004, fibi:  0.000012, percent:       0.33
n=26, fib: 0.000004, fibi:  0.000011, percent:       0.34
n=27, fib: 0.000004, fibi:  0.000011, percent:       0.35
n=28, fib: 0.000004, fibi:  0.000012, percent:       0.32
n=29, fib: 0.000004, fibi:  0.000012, percent:       0.33
n=30, fib: 0.000004, fibi:  0.000013, percent:       0.31
n=31, fib: 0.000004, fibi:  0.000012, percent:       0.34
n=32, fib: 0.000004, fibi:  0.000012, percent:       0.33
n=33, fib: 0.000004, fibi:  0.000013, percent:       0.30
n=34, fib: 0.000004, fibi:  0.000012, percent:       0.34
n=35, fib: 0.000004, fibi:  0.000013, percent:       0.31
n=36, fib: 0.000004, fibi:  0.000013, percent:       0.31
n=37, fib: 0.000004, fibi:  0.000014, percent:       0.29
n=38, fib: 0.000004, fibi:  0.000014, percent:       0.29
n=39, fib: 0.000004, fibi:  0.000013, percent:       0.31
n=40, fib: 0.000004, fibi:  0.000014, percent:       0.29

Weiteres Beispiel für Rekursion

Ein weiteres interessantes Beispiel für rekursive Programmierung ist das Spiel "Türme von Hanoi". Wir haben diesem Beispiel ein eigenes Kapitel gewidmet: Türme von Hanoi

Übungen

  1. Schreibe eine rekursive Version der Funktion f(n) = 3 * n, also eine Funktion, die die Vielfachen von 3 berechnet

  2. Schreibe eine rekursive Python-Funktion, welche die Summe der ersten n ganzen Zahlen zurückliefert.
    (Hinweis: Diese Funktion sieht ähnlich wie die Fakultätsfunktion aus!

  3. Schreibe eine Funktion, die das Pascalsche Dreick implementiert:

    1
    1    1
    1    2    1
    1    3    3    1
    1    4    6    4    1
    1    5    10    10    5    1

  4. Die Fibonacci-Zahlen verbergen sich auch innerhalb des Pascalschen Dreiecks. Wenn man die farbig markierten Zahlen im folgenden Pascalschen Dreieck aufsummiert, erhält man die 7. Fibonacci-Zahl:

    1
    1    1
    1    2    1
    1    3    3    1
    1    4    6    4    1
    1    5    10    10    5    1
    1    6    15    20    15    6    1

    Schreibe ein rekursives Programm, d.h. rekursive Funktion, die die Fibonacci-Zahlen aus einem Pasclaschen Dreieck heraus berechnet.

  5. Schreibe eine rekursive Funktion in Python für das Sieb des Eratosthenes.
    Das Sieb des Eratosthenes ist ein einfacher Algorithmus zur Berechnung aller Primzahlen bis zu einer bestimmten natürlichen Zahl. Dieser Algorithmus geht auf den alten griechischen Mathematiker Eratosthenes zurück.
    Algorithmus zum Finden aller Primzahlen kleiner einer gegebenen natürlichen Zahl n:
    1. Erzeuge eine List der natürlichen Zahlen von 2 bis n: 2, 3, 4, ..., n
    2. Starte mit einem Zähler i mit dem Wert 2, d.h. die erste Primzahl
    3. Beginnend mit i+i, inkrementiere jeweils um i und lösche alle so erhaltenen Zahlen aus der Liste, falls vorhanden, also die Zahlen 2*i, 3*i, 4*i, und so weiter
    4. Finde die erste auf i folgende Zahl in der Liste. Dies ist die nächste Primzahl.
    5. Setze i auf den im letzten Schritt gefundenen Wert.
    6. Wiederhole die Schritte 3, 4 und 5 bis i größer als n ist. (Als Verbesserung: Es genügt bis zur Quadradwurzel von n zu gehen)
    7. Alle Zahlen, die noch in der List sind, sind Primzahlen.
    Wenn wir uns den obigen Algorithmus genauer anschauen, sehen wir, dass wir ineffizient sind. So versuchen wir zum Beispiel die Vielfachen von 4 zu entfernen, obwohl die bereits durch die Vielfachen von 2 entfernt worden sind. Man erkennt, dass es genügt, die Vielfachen der Primzahlen bis zu der Quadradwurzel von n zu entfernen. Diese Menge kann man rekursiv konstruieren.

  6. Schreibe eine rekursive Funktion find_index(), die für einen Wert n den Index aus der Fibonacci-Folge zurückliefert, falls n eine Fibonacci-Zahl ist, und ansonsten, also wenn n kein Element der Folge ist, -1 zurückliefert.
    Für eine Fibonacci-Zahl n gilt also:
    fib(find_index(n)) == n
  7. Die Summe der Quadrate zweier aufeinanderfolgender Fibonacci-Zahlen ist ebenfalls wieder eine Fibonacci-Zahl, man sieht dies zum Beispiel bei 2 und 3, denn 2*2 + 3*3 ergibt 13 was Fib(7) entspricht.
    Benutze die Funktion aus der vorigen Aufgabe, um die Position der Summe der Quadrate aus zwei aufeinanderfolgenden Fibonacci-Zahlen in der Folge zu finden.

    Mathematische Erklärung:
    Seien a und b zwei aufeinanderfolgende Fibonacci-Zahlen. Die Fibonacci-Folge die mit "a" startet, sieht wie folgt aus:
    0              a
    1              b
    2          a + b	
    3	  a + 2b
    4 	 2a + 3b
    5        3a + 5b
    6        5a + 8b
    
    Wir erkennen, dass die Fibonacci-Zahlen als Faktoren von a und b erscheinen. Das n-te Element dieser Folge kann mit folgender Formel berechnet werden:
    F(n) = Fib(n-1)* a + Fib(n) * b
    
    Daraus folgt, dass für eine natürliche Zahl n mit n > 1 das folgende gilt:
    Fib(2*n + 1) = Fib(n)**2 + Fib(n+1)**2
    

Lösungen zu den Übungen:

  1. Lösung zu unseren ersten Übung zur Rekursion:
    Mathematisch können wir es wie folgt formulieren:
    f(1) = 3,
    f(n+1) = f(n) + 3


    Die Funktion in Python:
    def mult3(n):
        if n == 1:
            return 3
        else:
            return mult3(n-1) + 3
    
    for i in range(1,10):
        print(mult3(i))
    
  2. Lösung zur zweiten Übung:
    def sum_n(n):
        if n== 0:
            return 0
        else:
            return n + sum_n(n-1)
    

  3. Python-Programm zur Berechnung des Pacalschen Dreiecks:
    def pascal(n):
        if n == 1:
            return [1]
        else:
            line = [1]
            previous_line = pascal(n-1)
            for i in range(len(previous_line)-1):
                line.append(previous_line[i] + previous_line[i+1])
            line += [1]
        return line
    
    print(pascal(6))
    
    Alternativ können wir eine Lösung mit List Comprehension schreiben:
    def pascal(n):
        if n == 1:
            return [1]
        else:
            p_line = pascal(n-1)
            line = [ p_line[i]+p_line[i+1] for i in range(len(p_line)-1)]
            line.insert(0,1)
            line.append(1)
        return line
    
    print(pascal(6))
    

  4. Berechnung der Fibonacci-Zahlen aus dem Pascalschen Dreieck:
    def fib_pascal(n,fib_pos):
        if n == 1:
            line = [1]
            fib_sum = 1 if fib_pos == 0 else 0
        else:
            line = [1]
            (previous_line, fib_sum) = fib_pascal(n-1, fib_pos+1)
            for i in range(len(previous_line)-1):
                line.append(previous_line[i] + previous_line[i+1])
            line += [1]
            if fib_pos < len(line):
                fib_sum += line[fib_pos]
        return (line, fib_sum)
    
    def fib(n):
        return fib_pascal(n,0)[1]
    
    # and now printing out the first ten Fibonacci numbers:
    for i in range(1,10):
        print(fib(i))
    

  5. Iteratuve-Lösung für das Sieb des Eratosthenes für die ersten 100 Zahlen:
    from math import sqrt
    
    def sieve(n):
    	# returns all primes between 2 and n	
    	primes = list(range(2,n+1))
    	max = sqrt(n)
    	num = 2
    	while num < max:
    		i = num
    		while i <= n:
    			i += num
    			if i in primes:
    				primes.remove(i)
    		for j in primes:
    			if j > num:
    				num = j
    				break			
    	return primes
    	
    print(sieve(100))
    

    In diesem Kapitel unseres Python-Tutoirals geht es jedoch um rekursive Funktionen und in der Aufgabenstellung haben wir auch bei der Berechnung der Primzahlen einen rekursiven Algorithmus verlangt. Um die folgende Lösung besser verstehen zu können, empfehlen wir unser Kapitel über Listen-Abstraktion (List Comprehension) zu Rate zu ziehen:
    from math import sqrt
    
    def primes(n):
        if n == 0:
            return []
        elif n == 1:
            return []
        else:
            p = primes(int(sqrt(n)))
            no_p = [j for i in p for j in range(i*2, n + 1, i)]
            p = [x for x in range(2, n + 1) if x not in no_p]
            return p
    
    
    print(primes(100))
    

  6. memo = {0:0, 1:1}
    def fib(n):
        if not n in memo:
            memo[n] = fib(n-1) + fib(n-2)
        return memo[n]
    
    def find_index(*x):
    	""" finds the natural number i with fib(i) = n """
    	if len(x) == 1:
    		# started by user
    		# find index starting from 0
    		return find_index(x[0],0)
    	else:
    		n = fib(x[1])
    		m = x[0]
    		if  n > m:
    			return -1
    		elif n == m:
    			return x[1]
    		else:
    			return find_index(m,x[1]+1)
    

  7.  
    # code from the previous example with the functions fib() and find_index()
    
    print(" index of a |    a |     b | sum of squares | index ")	
    print("=====================================================")
    for i in range(15):
    	square = fib(i)**2 + fib(i+1)**2
    	print( " %10d |  %3d |   %3d | %14d | %5d " % (i, fib(i), fib(i+1), square, find_index(square)))
    
    
    Die Ausgabe für das vorige Skript sieht wie folgt aus:
     index of a |    a |     b | sum of squares | index 
    =====================================================
              0 |    0 |     1 |              1 |     1 
              1 |    1 |     1 |              2 |     3 
              2 |    1 |     2 |              5 |     5 
              3 |    2 |     3 |             13 |     7 
              4 |    3 |     5 |             34 |     9 
              5 |    5 |     8 |             89 |    11 
              6 |    8 |    13 |            233 |    13 
              7 |   13 |    21 |            610 |    15 
              8 |   21 |    34 |           1597 |    17 
              9 |   34 |    55 |           4181 |    19 
             10 |   55 |    89 |          10946 |    21 
             11 |   89 |   144 |          28657 |    23 
             12 |  144 |   233 |          75025 |    25 
             13 |  233 |   377 |         196418 |    27 
             14 |  377 |   610 |         514229 |    29