Fibonacci-reeks in Python: leer en verken codeertechnieken

De Fibonacci-reeks is een leuke manier om te blijven oefenen met Python. In dit artikel leer je hoe je de Fibonacci-reeks in Python implementeert met verschillende Python-technieken, van het schrijven van efficiënte functies en omgaan met recursie tot het toepassen van objectgeoriënteerde principes voor meer geoptimaliseerde oplossingen. 

Ben je helemaal door de stof heen, volg dan onze cursus Writing Functions in Python om concepten als scope en foutafhandeling te versterken, of probeer onze cursus Intermediate Object-Oriented Programming in Python om te leren over overerving en basisklassen. Laten we nu aan de slag gaan met de Fibonacci-reeks.

Snel antwoord

De Fibonacci-reeks begint met 0 en 1, waarbij elk getal de som is van de twee voorgaande. De eenvoudigste manier om deze in Python te genereren is met een lus:

n = 10
a, b = 0, 1

fibonacci_numbers = []

for _ in range(n):  
    fibonacci_numbers.append(str(a)) 
    a, b = b, a + b

print(' '.join(fibonacci_numbers))

# This prints the first 10 Fibonacci numbers
# 0 1 1 2 3 5 8 13 21 34Mogelijk gemaakt door

Wat is de Fibonacci-reeks?

De Fibonacci-reeks is een wiskundig concept dat in veel gebieden van wetenschap en natuur voorkomt. Het is een reeks getallen waarbij elk getal de som is van de twee voorgaande, beginnend met 0 en 1. Dit patroon vormt de basis voor toepassingen in velden zoals informatica en finance. 

Twee hoofdkenmerken definiëren de Fibonacci-reeks: de recursieve structuur van de reeks en de relatie met de gulden snede.

Recursieve aard van de Fibonacci-reeks

De Fibonacci-reeks begint met 0 en 1. Elk nieuw getal is de som van de twee getallen ervoor. Bijvoorbeeld:

0 + 1 = 1

1 + 1 = 2

1 + 2 = 3

2 + 3 = 5

3 + 5 = 8

5 + 8 = 13

En zo verder. 

Wiskundig schrijven we dit als F(n) = F(n-1) + F(n-2). De reeks bouwt zichzelf op door steeds de laatste twee getallen op te tellen. De eerste twee getallen, 0 en 1, zijn het startpunt of de basisgevallen. Zonder deze zou de reeks niet werken.

Dit recursieve patroon dient als basis voor sommige algoritmen in de informatica. Zo werkt recursie in programmeren op deze reeks bij het oplossen van problemen zoals het genereren van Fibonacci-getallen of het opdelen van taken in kleinere, beheersbare stukken.

Verband met de gulden snede 

De Fibonacci-reeks is nauw verbonden met de gulden snede, een irrationeel getal weergegeven door φ (de waarde is ongeveer 1,618). Als je een Fibonacci-getal deelt door het voorgaande, komt de verhouding steeds dichter bij φ. Bijvoorbeeld:

5 ÷ 3 ≈ 1,666

8 ÷ 5 ≈ 1,6

13 ÷ 8 ≈ 1,625

Hoe verder je gaat, hoe dichter je bij 1,618 komt. Dit is geen toeval — de verhouding komt van nature voor in de Fibonacci-reeks door de manier waarop de getallen groeien.

Euclides beschreef het in het oude Griekenland als de extreme en middelste reden. Sindsdien is het in verband gebracht met patronen in de natuur, zoals spiralen in schelpen en bloemen, maar ook in kunst en architectuur.

Gulden snede in kunst. Bron

Praktische toepassingen van de Fibonacci-reeks

De Fibonacci-reeks duikt op verrassende manieren op in veel vakgebieden. Laten we focussen op twee van de meest opvallende toepassingen: de patronen in de natuur en het gebruik in de informatica.

Fibonacci in de natuur

Je ziet de Fibonacci-reeks overal in de natuur. Kijk naar bloemen — het aantal bloemblaadjes komt vaak overeen met Fibonacci-getallen. Zo kunnen madeliefjes 34, 55 of 89 blaadjes hebben, en lelies vaak 3, 5 of 8. Deze patronen helpen planten zo te groeien dat ze optimaal zonlicht en regen opvangen.

Ook spiralen in dennenappels en zonnebloemen volgen Fibonacci-getallen. De rangschikking van zaden in een zonnebloem komt bijvoorbeeld overeen met de reeks. Het is fascinerend hoe iets simpels als twee getallen optellen zoveel van de natuurlijke wereld kan beschrijven.

Fibonacci in de informatica

De Fibonacci-reeks speelt ook een sleutelrol in algoritmen en datastructuren. Zo worden Fibonacci-getallen gebruikt in zoekalgoritmen om problemen efficiënt op te splitsen in kleinere delen. De reeks ligt zelfs ten grondslag aan Fibonacci-heaps, een type datastructuur dat bepaalde bewerkingen versnelt, zoals het vinden van het kortste pad in een netwerk.

Hier is een eenvoudig voorbeeld van hoe je een Fibonacci-reeks in Python kunt genereren:

def fibonacci(n):
	if n <= 1:
		return n
	return fibonacci(n - 1) + fibonacci(n - 2)

# Example usage
fibonacci_numbers = []

for i in range(10):
	fibonacci_numbers.append(str(fibonacci(i)))

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Mogelijk gemaakt door

Deze recursieve functie laat zien hoe de Fibonacci-reeks wordt opgebouwd. Hoewel recursie makkelijk te begrijpen is, zijn er ook geoptimaliseerde varianten, zoals dynamic programming, om Fibonacci-getallen veel sneller te berekenen.

In cryptografie kunnen Fibonacci-getallen helpen bij het genereren van veilige sleutels. En in kunstmatige intelligentie optimaliseren ze neurale netwerken om te verbeteren hoe algoritmen leren en zich aanpassen. 

Andere veelvoorkomende voorbeelden

Hier zijn nog een paar voorbeelden van hoe deze reeks voorkomt in het dagelijks leven en in gespecialiseerde domeinen:

• In de kunst: de Fibonacci-reeks wordt al eeuwen gebruikt door kunstenaars en architecten. Beroemde bouwwerken zoals het Parthenon bevatten deze verhoudingen omdat ze van nature aangenaam zijn voor het oog.
• In de muziek: componisten gebruiken Fibonacci-getallen om ritmes en melodieën te creëren. Zo koppelen ze bijvoorbeeld hele noten aan 1, halve noten aan 2 en kwartnoten aan 3 om harmonieuze patronen te maken.
• In de handel: aandelenhandelaren passen Fibonacci-getallen toe om markttrends te analyseren. Ze gebruiken ze om potentiële prijsniveaus te voorspellen waar aandelen kunnen omkeren, wat helpt bij het bepalen wanneer te kopen of te verkopen.
• In de natuurkunde: in de kwantumfysica zijn Fibonacci-patronen waargenomen in de interacties en het gedrag van deeltjes, wat laat zien hoe deze reeksen zelfs op de allerkleinste schalen van de natuur voorkomen.

De Fibonacci-reeks implementeren in Python

Omdat Python meerdere manieren biedt om de Fibonacci-reeks te genereren, heb ik de meest gebruikte methoden stap voor stap met voorbeelden besproken.

Een iteratieve methode gebruiken

De iteratieve methode is een van de eenvoudigste manieren om de Fibonacci-reeks te genereren. Het gebruikt een lus om elke term in de reeks te berekenen, wat het geheugen-efficiënter maakt dan recursieve methoden. Zo werkt het:

Ik zet twee variabelen, a en b, op 0 en 1. Deze staan voor de eerste twee getallen in de reeks. Vervolgens gebruik ik een for-lus om de volgende getallen te berekenen. Ik update a met de waarde van b, en b wordt de som van de vorige a en b.

Hier is Python-code hiervoor:

n = 10
a, b = 0, 1

fibonacci_numbers = []

for _ in range(n):
    fibonacci_numbers.append(str(a))
    a, b = b, a + b

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Mogelijk gemaakt door

Als je in plaats van een for-lus een while-lus wilt gebruiken, kun je de code zo schrijven:

# Number of terms to print in the Fibonacci series
n = 10

# Initialize the first two terms
a, b = 0, 1
i = 0

fibonacci_numbers = []

while i < n:
	fibonacci_numbers.append(str(a))
	# Update the terms
	a, b = b, a + b
	i += 1

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Mogelijk gemaakt door

Beide methoden zijn super makkelijk te begrijpen en daarom perfect voor beginners. 

Een recursieve methode gebruiken

De recursieve methode is een andere manier om Fibonacci-getallen te genereren. Voor grotere reeksen is het niet zo snel als de iteratieve methode, maar het is een geweldige manier om de logica achter de opbouw van de reeks te begrijpen.

Ik maak bijvoorbeeld een functie genaamd fibonacci_recursive. Deze functie neemt een getal n als invoer. Als n 0 of 1 is, geeft de functie n terug. Dit zijn de basisgevallen die aangeven wanneer de recursie moet stoppen. Voor elk ander getal roept de functie zichzelf aan om de twee voorgaande getallen te berekenen en deze bij elkaar op te tellen.

Hier is de code hiervoor:

def fibonacci_recursive(n):
	if n <= 1:
		return n
	else:
		return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

num_terms = 10
fibonacci_numbers = []
for i in range(num_terms):
	fibonacci_numbers.append(str(fibonacci_recursive(i)))

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Mogelijk gemaakt door

Deze methode werkt goed voor kleine reeksen, maar kan traag worden naarmate de reeks groeit omdat dezelfde waarden meerdere keren opnieuw worden berekend.

Een geoptimaliseerde recursieve methode met caching

Om de inefficiëntie van eenvoudige recursie op te lossen, gebruik ik vaak caching. Python’s lru_cache slaat eerder berekende waarden op zodat de functie het werk niet opnieuw hoeft te doen.

Zo pak ik het aan:

from functools import lru_cache

@lru_cache(maxsize = None)
def fib_cache(n):
    if n == 0:
        return 0  
    elif n == 1:
        return 1
    else:
        return fib_cache(n-1) + fib_cache(n-2)

print(f"The Fibonacci Number is {fib_cache(10)}")

# The Fibonacci Number is 55Mogelijk gemaakt door

Deze aanpak combineert de duidelijkheid van recursie met de efficiëntie van caching.

Meer geavanceerde manieren om de Fibonacci-reeks in Python te doen

Als je op zoek bent naar andere manieren om Fibonacci-getallen te berekenen, zijn hier een paar meer geavanceerde technieken:

Matrixmachtsverheffing

Matrixmachtsverheffing is een van de efficiëntste manieren om Fibonacci-getallen te berekenen voor grote waarden van n. In plaats van termen steeds opnieuw te berekenen, gebruikt deze methode matrixvermenigvuldiging om resultaten in logaritmische tijd te krijgen.

Zo heb ik dit in Python geïmplementeerd:

import numpy as np

def fibonacci_matrix(n):
	def matrix_power(matrix, power):
		return np.linalg.matrix_power(matrix, power)
	if n == 0:
		return 0
	matrix = np.array([[1, 1], [1, 0]])
	result = matrix_power(matrix, n-1)
	return result[0][0]

fibonacci_numbers = []

for i in range(10):
	fibonacci_numbers.append(str(fibonacci_matrix(i)))

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Mogelijk gemaakt door

In deze code geldt: als n 0 is, wordt 0 teruggegeven als basisgeval. Voor andere waarden wordt de matrix met de macht (n-1) verheven via numpy’s matrix_power-functie. Het Fibonacci-getal op positie n staat in het linkerboven-element van de resulterende matrix.

Formule van Binet

De formule van Binet berekent direct het nde Fibonacci-getal zonder iteratie of recursie. Ze is gebaseerd op de gulden snede, φ, en gebruikt een wiskundige uitdrukking om het resultaat meteen te berekenen.

De formule is:

Waarbij:

• φ = (1 + √5) / 2​​, de gulden snede.
• 1 - φ is de geconjugeerde van φ.

Hier is de Python-code voor de formule van Binet:

import math

def fibonacci_binet(n):
    phi = (1 + math.sqrt(5)) / 2
    return round((phi ** n - (1 - phi) ** n) / math.sqrt(5))

# Find the 10th Fibonacci number
n = 10
result = fibonacci_binet(n)
print(f"The Fibonacci Number of {n}th term is {result}" )

# The Fibonacci Number of 10th term is 55Mogelijk gemaakt door

In deze code berekent de functie fibonacci_binet(n) het nde Fibonacci-getal met de formule van Binet. In de functie bereken ik phi (de gulden snede) als (1 + math.sqrt(5)) / 2, waarbij ik math.sqrt() gebruik voor de wortel uit 5. De formule (phi ** n - (1 - phi) ** n) / math.sqrt(5) wordt vervolgens toegepast om het nde Fibonacci-getal direct te vinden. Daarna gebruik ik de functie round() om kleine afrondingsfouten met drijvende komma op te vangen.

Arrays

Je kunt zelfs arrays gebruiken om de volledige Fibonacci-reeks te genereren en op te slaan. Dit is handig wanneer je meerdere termen tegelijk nodig hebt.

Hier is de code hiervoor:

def fibonacci(n):
    if n <= 0:
        return "Incorrect Output"
    data = [0, 1]  # Initialize list with first two Fibonacci terms: 0 and 1
    if n > 2:
        for i in range(2, n):  # Start loop from the third term
            data.append(data[i-1] + data[i-2])  # Calculate next term as sum of previous two
    return data[n-1]  # Return the nth term

print(f"Fibonacci Number: {fibonacci(10)}")

# Fibonacci Number: 34Mogelijk gemaakt door

Backtracking

Backtracking is een andere optie die ik kan gebruiken, vooral als ik recursie wil combineren met memoization voor betere prestaties.

Hier is de code hiervoor:

def fibonacci_backtracking(n, computed ={0: 0, 1: 1}):
    if n in computed:
        return computed[n]
    computed[n] = fibonacci_backtracking(n - 1) + fibonacci_backtracking(n - 2)
    return computed[n]

n = 10
result = fibonacci_backtracking(n)
print(f"The {n}th Fibonacci term is {result}")

# The 10th Fibonacci term is 55Mogelijk gemaakt door

Complexiteit van Fibonacci-algoritmen in Python

We hebben heel wat voorbeelden doorgenomen! Laten we nu naar de verschillen kijken qua tijds- en ruimtecomplexiteit. Zoals we al noemden, zijn sommige methoden snel maar gebruiken ze meer geheugen, terwijl andere trager zijn maar minder ruimte nodig hebben. Ik heb deze tabel voorbereid om de efficiëntie van elke aanpak te vergelijken.

In de bovenstaande tabel betekent elke tijds- en ruimtecomplexiteit het volgende:

Tijdscomplexiteit

• O(n): Het algoritme doorloopt de reeks één keer door een vast aantal bewerkingen per element uit te voeren. De benodigde tijd groeit lineair met de invoergrootte n.

• O(1): Het Fibonacci-getal wordt berekend met een vast aantal bewerkingen, zonder iteratie of recursie.

• O(2ⁿ): Het algoritme maakt twee recursieve aanroepen voor elke invoer, wat leidt tot exponentiële groei in het aantal functieaanroepen naarmate n toeneemt.

• O(log n): De looptijd groeit in verhouding tot de logaritme van de invoergrootte n.

Ruimtecomplexiteit

• O(n): Het algoritme gebruikt geheugen dat rechtstreeks meegroeit met het aantal invoeren n. Hier vereist elk element een vaste hoeveelheid ruimte.

• O(1): Het geheugengebruik blijft constant, ongeacht de invoergrootte.

• O(2ⁿ): Er wordt exponentiële ruimte gebruikt door het ontstaan van nieuwe toestanden voor elke vertakking.

• O(log n): Tussentijdse matrixvermenigvuldigingen gebruiken logaritmisch geheugen.

Tot slot

Zoals je hebt gezien, kun je in Python Fibonacci-getallen berekenen met veel verschillende methoden, van eenvoudige lussen tot geavanceerde technieken zoals matrixmachtsverheffing en de formule van Binet. Elke methode heeft zijn sterke punten en afwegingen.

Ik hoop dat je iets hebt geleerd over zowel de Fibonacci-reeks als over programmeren in Python. Wil je meer ontdekken over Python en aanverwante onderwerpen, bekijk dan onze cursus Introduction to Python. Je kunt ook onze volledige Python Developer-carrièreroute proberen en programmeertechnieken leren en zelfs je eigen packages gaan ontwikkelen!