En stor fordel med rekursjon er at vi kan kode en funksjonsdefinisjon så å si direkte, uten å behøve å tenke på løkker og løkkevariable. Rekursjon gir ofte enkle og elegante løsninger. Sammenlikn for eksempel den iterative og rekursive varianten av fakultetsfunksjonen vist i eksempel 1:
Eksempel 1:
Iterativ versjon:
def fakultet(n):
"""Beregner n! ved iterasjon"""
fakt = 1
for m in range(2, n + 1):
fakt *= m
return fakt
Rekursiv versjon:
def fakultet(n):
"""Beregner n! ved rekursjon"""
if n == 0:
return 1
else:
return n * fakultet(n - 1)
Av og til kan det faktisk være vanskelig å finne en løsning som ikke er rekursiv. Ulempen med rekursjon er at det er atskillig mindre effektivt enn løkker, fordi å håndtere funksjonskall krever mye ekstra arbeid, såkalt overhead, av datamaskinen. I praksis vil det også finnes en grense for hvor mange funksjonskall vi kan kjede etter hverandre. Går vi over grensa, får vi en feilmelding. I Python ligger denne grensa på rundt 1000.
Av og til kan rekursjon også være en håpløst ineffektiv løsning. Vi skal illustrere dette med en funksjon for å beregne fibonaccitall. Fibonaccitallene er 1, 1, 2, 3, 5, 8, …, en tallfølge der de to første tallene er 1, og hvert tall deretter er lik summen av de to foregående.
En iterativ versjon av en funksjon for å beregne fibonaccitall er vist i eksempel 2.
Eksempel 2:
def fibonacci(n):
"""Beregner fibonaccitall nummer n ved iterasjon."""
pre_fibo = 1
fibo = 1
for _ in range(n - 2):
fibo, pre_fibo = fibo + pre_fibo, fibo
return fibo
Hvis vi har funksjonen i eksempel 2, og i hovedprogrammet skriver
for n in range(1, 101):
print(f"Fibonacctitall {n} er {fibonacci(n)}")
skrives de 100 første fibonaccitallene kjapt ut.
I eksempel 2 representerer fibo fibonaccitallet og pre_fibo tallet før fibonaccitallet. Disse settes i utgangspunktet til 1, siden det første og andre fibonaccitallet er 1. Hvis funksjonen kalles opp med n lik 1 eller 2, gjennomløpes ikke løkka, og fibo beholder verdien 1. Hvis n er 3 eller større, gjennomløpes løkka, der fibo blir satt lik fibo + pre_fibo og pre_fibo blir satt lik fibo.
Det krever imidlertid en del tankearbeid å forstå logikken i eksempel 2. Den rekursive varianten i eksempel 3 er mye enklere å forstå.
Eksempel 3:
def fibonacci(n):
"""Beregner fibonaccitall nummer n ved rekursjon."""
if n <= 2:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
I eksempel 3 benytter vi definisjonen av fibonaccitall direkte. Hvis funksjonen kalles opp med n lik 1 eller 2, er returverdien 1. Hvis n er 3 eller større, er returverdien summen av de to foregående fibonaccitallene.
Men hvis vi nå i hovedprogrammet igjen skriver
for n in range(1, 101):
print(f"Fibonacctitall {n} er {fibonacci(n)}")
ser vi at det er noe som ikke fungerer. Tallene skrives ut langsommere og langsommere, og i nærheten av fibonaccitall 40 stopper det nesten helt opp. Sjekk gjerne ut dette selv.
Grunnen er at vi har to rekursive kall i funksjonen, nemlig fibonacci(n – 1) og fibonacci(n – 2), slik at vi for hvert rekursjonskall genererer to nye, og vi får en eksponentiell vekst i kompleksitet. Samme fibonaccitall beregnes om og om igjen. Trestrukturen under viser hvordan funksjonskallene skjer når vi skal beregne fibonaccitall nummer 6:
Vi ser at fibonaccitall nummer 2 beregnes hele 5 ganger.
Rekursjon bør vi generelt ikke bruke hvis et rekursivt kall genererer mer enn ett nytt.
Kilder
-
- Matthes A. (2019). Python Crash Course. no starch press