English web site
Dubbelrekursion
MOVIE-URL: https://www.youtube.com/embed/Z1ekt1iW2Ls
Vi har tidigare skrivit funktioner som med hjälp av renodlad iteration eller renodlad rekursion bearbetat alla element i en sträng eller i en "platt" lista, en lista som inte är nästlad. I det fallet har behöver vi bara gå genom strängen eller listan i en dimension, från det första elementet till det sista.
Vi har också tittat på fallet med nästlade listor. Listor är ju mer generella än strängar och kan innehålla i princip vad som helst, t.ex. andra listor:
>>> s1 = [1, 'two', 3, 4]
>>> s2 = [1, 'two', [3, 4, 'five'], [True]]
>>> len(s2)
4
>>> type(s2[2])
<class 'list'>
När vi skulle beräkna summan av alla heltal på alla nivåer i en nästlad lista blev det mer komplicerat att försöka använda renodlad iteration. Det hade faktiskt hade varit möjligt, med hjälp av tekniker vi inte diskuterar i den här kursen, men det blir mycket enklare att använda rekursion för att hantera de nästlade listorna. Samma sak gäller för alla strukturer som på något sätt är godtyckligt nästlade. Då gjorde vi på detta sätt:
def sum_of_any_level_list(seq):
sum = 0
for element in seq:
# isinstance(elem, datatype) är en funktion som avgör om elem är av typen datatype
if isinstance(element, int):
sum += element
else:
# The element must be a nested list
sum += sum_of_any_level_list(element)
return sumHär har vi alltså inte någon renodlad lösning utan vi har blandat rekursion (på djupet) och iteration (inom varje nivå).
Nu ska vi titta på hur man istället använder rekursion "på båda hållen" -- rekursion för att hitta nästa element på samma nivå, och rekursion för att hantera nästlade nivåer av listor. Detta kan vi kalla dubbelrekursion, och det ser ut så här (mer förklaringar i nästa avsnitt):
def sum_of_any_level_list(seq):
if not seq:
return 0
elif isinstance(seq[0], int):
# Första värdet är ett heltal, så vi kan plocka dess värde direkt
sum_of_first_element = seq[0]
sum_of_rest_of_list = sum_of_any_level_list(seq[1:])
return sum_of_first_element + sum_of_rest_of_list
else:
# Första värdet är en lista, så vi måste summera dess värden
# *och* summera värdena i resten av listan
sum_of_first_element = sum_of_any_level_list(seq[0])
sum_of_rest_of_list = sum_of_any_level_list(seq[1:])
return sum_of_first_element + sum_of_rest_of_listVi kan så klart också vända på typkontrollen så att vi testar om värdet är en lista. Detta kan vara bättre när man kan ha flera typer av element.
def sum_of_any_level_list(seq):
if not seq:
return 0
elif isinstance(seq[0], list):
sum_of_first_element = sum_of_any_level_list(seq[0])
sum_of_rest_of_list = sum_of_any_level_list(seq[1:])
return sum_of_first_element + sum_of_rest_of_list
else:
sum_of_first_element = seq[0]
sum_of_rest_of_list = sum_of_any_level_list(seq[1:])
return sum_of_first_element + sum_of_rest_of_listOch så måste vi inte alltid mellanlagra värden i variabler, även om det kan förbättra läsbarheten i många fall:
def sum_of_any_level_list(seq):
if not seq:
return 0
elif isinstance(seq[0], list):
return sum_of_any_level_list(seq[0]) + sum_of_any_level_list(seq[1:])
else:
return seq[0] + sum_of_any_level_list(seq[1:])Beräkna den totala längden i en nästlad lista
Vi ska nu skriva en funktion som använder sig av dubbelrekursion för att beräkna den totala längden av en lista och dess underlistor.
def length(seq):
if not seq:
return 0
# isinstance(elem, datatype) är en funktion som avgör om elem är av typen datatype
elif isinstance(seq[0], list):
return length(seq[0]) + length(seq[1:])
else:
return 1 + length(seq[1:])Skillnaden mot hur vi har gjort rekursion tidigare är alltså att nu kollar vi även om det första elementet i listan är en lista, och i så fall anropar vi funktionen på både den underlistan och listan med resten av elementen.
Vad händer egentligen i programmet när vi kör det? Här är ser vi ordningen som anropen sker i när vi anropar len2([1, 'two', [3, 4, 'five'], [True]]).
a: len2([1, 'two', [3, 4, 'five'], [True]])
b: len2(['two', [3, 4, 'five'], [True]])
c: len2([[3, 4, 'five'], [True]])
d: len2([3, 4, 'five'])
e: len2([4, 'five'])
f: len2(['five'])
g: len2([])
g: => 0
f: => 1
e: => 2
d: => 3
d: len2([[True]])
e: len2([True])
f: len2([])
f: => 0
e: => 1
d: => 1
c: => 4
b: => 5
a: => 6
Exempel
Vi vill ha en funktion remove som kan ta bort alla förekomster av ett element ur en lista. Listan kan innehålla underlistor, och dessa ska också gås igenom. Lösningen ska egentligen bygga upp en ny lista utan förekomsterna av det givna elementet, snarare än att plocka bort från den befintliga listan.
Vi tänker oss i första hand en rekursiv lösning och gör följande fallanalys. Hur kan man tänka sig att olika listor börjar och hur ska vi behandla dem?
| Första elementet i listan | Behandling |
|---|---|
| Tom lista | Returnera tom lista |
| Underlista | Bearbeta underlistan och resten |
| Elementet vi ska ta bort | Fortsätt med resten |
| Element som ska vara kvar | Bygg ihop och fortsätt med resten |
Rekursiv lösning
def remove(seq, x):
""" Removes all occurrences of x in the list seq and its sublists """
if not seq:
return []
elif isinstance(seq[0], list):
return [remove(seq[0], x)] + remove(seq[1:], x)
elif seq[0] == x:
return remove(seq[1:], x)
else:
return [seq[0]] + remove(seq[1:], x)Iterativ lösning
def remove(seq, x):
""" Removes all occurrences of x in the list seq and its sublists"""
result = []
for elem in seq:
if isinstance(elem, list):
result += [remove(elem, x)]
elif elem != x:
result += [elem]
return resultObservera att lösningen inte är helt iterativ.
Överkurs: För att en helt iterativ lösning ska klara av godtyckligt djupa strukturer kan man manuellt spara undan funktionens tillstånd i en stack när man träffar på en nästlad struktur, och återställa funktionens tillstånd från stacken när man är klar med den nästlade strukturen. Detta leder till en hel del manuellt arbete som rekursionen istället tar hand om helt automatiskt -- funktionsanropet kommer i sig självt att spara undan nödvändig information på en sådan stack utan att vi behöver bry oss om detaljerna.
Sidansvarig: Peter Dalenius
Senast uppdaterad: 2021-12-03
