15. Dubbelrekursion

För att bearbeta elementen i en sammansatt datastruktur (strängar, listor, tupler, dictionaries) har vi tittat på ett par olika metoder. Iteration innebär att vi gör upprepning rakt och enkelt med hjälp av for. Rekursion innebär att vi skapar funktioner som anropar sig själva och steg för steg går igenom datastrukturen.

Detta funkar så länge datastrukturen inte innehåller något avancerat. Men listor kan ju innehålla andra listor. Det kan vi hantera med dubbelrekursion.

1. Strukturen för en lista med listor

En lista som inte innehåller några andra listor brukar vi kalla rak eller enkel. En lista som i sig innehåller andra listor brukar vi kalla nästlad eller djup. De listor som finns inuti den stora listan kallas underlistor. Det går i teorin att ha hur djupa listor som helst, med listor i listor i listor i listor...

I det här exemplet skapar vi två listor, seq1 som är en vanlig rak lista med fyra element och seq2 som också innehåller fyra element på toppnivån men där de två sista elementen är listor i sig.

>>> seq1 = [1, 'two', 3, 4]
>>> seq2 = [1, 'two', [3, 4, 'five'], [True]]
>>> len(seq2)
4
>>> type(seq22[2])
<class 'list'>

När vi ska skriva funktioner som bearbetar listor i listor kan det vara bra att försöka visualisera listans struktur. Listan seq2. med sina underlistor, kan vi visualisera så här:

Om vi steg för steg ska bearbeta den här strukturen är det ganska lätt att ta sig förbi de första två elementen. Men när vi kommer till det tredje måste vi göra två saker. Vi måste dels bearbeta underlistan, dels fortsätta framåt med huvudlistan. Det är därför det heter dubbelrekursion, för vi gör två saker.

2. Summera alla tal i en nästlad lista

Vi vill ha en funktion som kan gå igenom en godtyckligt djup lista (alltså en lista där det kan finnas hur djupa listor som helst) och summerar allt som är tal men ignorerar resten. Det här är svårt att lösa med bara iteration, men det är åtminstone genomförbart med rekursion. Ett sätt att kombinera båda teknikerna är att göra så här:

def sum_of_any_level_list(seq):
    sum = 0
    for element in seq:
        if isinstance(element, int):
            sum += element
        else:
            sum += sum_of_any_level_list(element)
    return sum

Hä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 åt båda hållen:

def sum_of_any_level_list(seq):
    if not seq:
        return 0
    elif isinstance(seq[0], int):
        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:
        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

Vi 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_list

Och så måste vi inte alltid mellanlagra värden i variabler, även om det kan förbättra läsbarheten i många fall. En mer kompakt variant är följande:

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:])

3. Beräkna den totala längden av 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 alla dess underlistor. Hur ska man tänka när man ska skriva en dubbelrekursion funktion? Ett sätt är att försöka strukturera upp alla möjliga fall. Vad är det för indata vi kan tänka oss kan komma in?

Den här fallanalysen motsvarar den if-sats som kommer utgöra hela funktionen och den blir alltså så här:

def length(seq):
    if not seq:
        return 0
    elif isinstance(seq[0], list): 
        return length(seq[0]) + length(seq[1:])
    else:
        return 1 + length(seq[1:])

Vad händer egentligen när vi kör den här funktionen? Det här är ett försök att illustrera alla anrop om vi skickar in listan seq2 som vi såg tidigare:

a: length([1, 'two', [3, 4, 'five'], [True]])
    b: length(['two', [3, 4, 'five'], [True]])
        c: length([[3, 4, 'five'], [True]])
            d: length([3, 4, 'five'])
                e: length([4, 'five'])
                    f: length(['five'])
                        g: length([])
                        g: => 0
                    f: => 1
                e: => 2
            d: => 3
            d: length([[True]])
                e: length([True])
                    f: length([])
                    f: => 0
                e: => 1
            d: => 1
        c: => 4
    b: => 5
a: => 6

På nivå d i den här spårningen ser vi att funktionen har anropats två gånger, en gång för att ta hand om underlistan och en gång för att ta hand om resten.

4. Ta bort ett element ur en nästlad lista

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?

Del rekursiva lösningen får vi genom att översätta tabellen med fallanalys till en if-sats:

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)

Som ett alternativ kan vi också tänka oss en lösning som är iterativ på toppnivån, men som anropar sig själv rekursivt när vi stöter på en underlista:

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 result

Sammanfattning

• Dubbelrekursion är ett sätt att bearbeta nästlade listor av godtyckligt djup. Vi anropar oss själva rekursivt två gånger: en gång för underlistan och en gång för resten av listan.
• För att konstruera en dubbelrekursiv funktion är det bra att börja med en tydlig fallanalys.
• Det går att bearbeta nästlade listor med en kombination av iteration och rekursion.