IDA - Institutionen för datavetenskap

Kursmaterial

Rekursion

Rekursiva funktioner är funktioner som anropar sig själva. Man kan se det som ett alternativ till loopar när man vill göra någonting om och om igen. Rekursion är mycket vanligt i vissa språk men inte särskillt vanligt i python. Anledningen till detta är att python har mycket andra bra och enkla sätt att loopa.

Ett exempel

Hur kan vi summera en lista med rekursion?

def sumlist(li):
    # print(li)
    if not li:
       return 0
    else:
       return li[0] + sumlist(li[1:])

print( sumlist([1,2,3,4,5]) )

Det som händer i koden ovan är av varje nivå av rekursionen plockar bort det första elementet i listan och skickar en slice av index 1+ till nästa nivå av rekursionen. När funktionen anropas med en tom lista så returneras 0 och rekusionen slutar. Då returneras alla värden och slås ihop. Testa att köra koden ovan. Testa också att ta bort kommentaren vid print i funktionen. Då kommer du kunna se hur listan du skickar in ser ut vid varje nivå av djup i rekursionen.

Testa att skriva en egen enkel funktion som löser ett trivialt problem som du sedan tidigare löst med en loop.

Vi använder vanligtvis rekursion när det är det smidigaste alternativet. Ett av de få tillfällena där detta är sant är när vi ska traversera (gå igenom) datastrukturer. Ett bra exempel är arbiträrt nestlade listor:

def sum_arb_list(li):
    tot = 0
    for x in li:
        if not isinstance(x, list):
            tot += x #Om x inte är en lista kan vi addera siffran till summan
        else:
            tot += sum_arb_list(x)
    return tot

tot=0
li = [3, [2, [3, 4], 5], 6, [7, 8]]
print(sum_arb_list(li))
tot=0
li = [4, 2, 3, 4, 5, 6, 7, 8]
print(sum_arb_list(li))

Denna funktion går igenom listorna element för element och anropar funktionen igen med dessa element tills dess att de individuella elementen inte längre är listor. Denna funktionalitet skulle vara mycket svår att implementera med en loop.

Detta bör vara en start när det kommer till att lära sig rekursion. För att skapa djupare förståelse bör du träna på att göra loopar som löser olika problem och traverserar datastrukturer. Hitta på dina egna problem och lös dessa!