TDDE44 Programmering, grundkurs

Föreläsning 3.1-3.2

Johan Falkenjack, johan.falkenjack@liu.se

Föreläsningsöversikt

• Att ta med sig från Laboration 2
• Laboration 3: En egen pokedex som hämtar data från webben
• Oföränderliga och föränderliga värden
• Variabler som referenser

• Nya klasser: tuple och dict
• Mer om dataabstraktion
• Nästlade datastrukturer
• Bearbetning av nästlade datastrukturer

• Rekursion

Att ta med sig från laboration 2

• När bör while- resp. for-loop användas?
• Namngivning av variabler, funktioner och parametrar
  • mönster, t.ex. for word in words
  • undvik allt för generella namn
• shebang-raden

for- loop eller while-loop?

• Mindre logistik om vi itererar över en sekvens med for:

values = list(range(100))

i = 0
while i < len(values):
    value = values[i]
    if value == 42:
        print("I found the answer!")
    i += 1

for value in values:
    if value == 42:
        print("I found the answer!")
        

I found the answer!
I found the answer!

• Notera att dessa loopar gör exakt samma sak.
• Jag gjorde två misstag när jag skrev while-exemplet utan att ens försöka göra fel.
• For-loopar är mer kortfattade och enklare att läsa.

for- loop eller while-loop?

• Behöver inte manuell loopvariabel med for:

i = 0
for value in values:
    if value == 42:
        print("I found the answer!")
    i += 1

• Behöver inte heller en explicit uppslagning.

Varför finns ens while-loopen?

• while-loopar är nödvändiga om man vill fortsätta loopa under vissa förutsättningar - villkor - snarare än över en viss sekvens.

import random

secret_word = random.choice(["apelsin", "banan", "citron"])
guess = None
tries = 0

while guess != secret_word:
    if guess != None:
        print("Fel!")
    guess = input("Gissa vilket ord jag tänker på: ")
    tries += 1
print("Rätt! Det tog " + str(tries) + " försök.")

Gissa vilket ord jag tänker på: apelsin
Fel!
Gissa vilket ord jag tänker på: banan
Rätt! Det tog 2 försök.

• Tveksamt om man ens kan hitta på ett sätt att lösa detta med en for-loop.
• Jag vill försöka, men nej.

Namngivning av funktioner och variabler

• Försök att använda beskrivande funktions- och variabelnamn.
  • Koden blir lättare att läsa.
• Använd verbliknande namn för funktioner
  • add_numbers(), calculate_volume(), load_file(), find_most_common_word()
• Använd substantiv till variabelnamn.
• Bra att döpa listor till substantiv i plural: words, values, names
• Vanligt mönster vid användning av for-loop:

for word in words:

Python-skript och shebang-raden

• För exekverbara textfiler i Linux (chmod u+x filnamn), om första raden börjar på #! (hash bang → shebang) kommer skalet att anta att efterföljande text på raden är sökvägen till den programtolk som ska användas på resten av filen
• Bash-skript
  • #!/bin/bash
• Python-skript
  • #!/usr/bin/env python3
• Perl-skript
  • #!/usr/bin/perl

Laboration 3

Del 1: Pythonuppgift 3

Del 2: Egen Pokedex; hämta information från webben

Kort om laboration 3, Del 2

• Hämta information från webben istället för från fil
• Nytt textbaserat data-format: JSON
• Webb-API:er - om URL:er vore funktioner som returnerar data
• PokeAPI - ett webb-API till en databas om Pokémon
• pokedex.py - skript som skriver ut information om en pokémon.

• Lektion 3: övningar inför Del 2
  • paketet requests för att hämta data från webben
  • JSON-data till dictionary

f-strängar

Enklare strängformattering i Python

Enklare formattering av strängar

• f-strängar, en sträng med f som prefix
  • f"Jag är en f-sträng"
• Kan innhålla uttryck innanför måsvingar, {}, som beräknas när strängen skapas.
• Exempel:

namn = "Guido"
f"Hej {namn}!"

'Hej Guido!'

f"Jag vet att svaret är {21*2}"

'Jag vet att svaret är 42'

Smidig utskrift av variabler

• Lägg till = efter ett uttryck inom {} i en f-sträng, så följer även själva uttrycket med när strängen skapas.

• Exempel:

my_value = 123
print(f"{my_value=}")

my_value=123

print(f"{40+2=}")

40+2=42

print(f"{my_value/2=}")

my_value/2=61.5

Värden och referenser

Oföränderliga värden

• I Python är strängar, heltal, flyttal, sanningsvärden, None och tupler oföränderliga (eng. immutable).
• Detta betyder att man inte kan ändra på dessa värden.
  • t.ex. så kan inte ändra värdet 5 till värdet 1, värdet 5 är alltid 5.
  • Python behandlar strängar på samma sätt; i Python kan vi inte ändra strängen "hej" till strängen "nej"

Vänta lite, vi har ju ändrat på både heltal och strängar!

Hur många försökte följande lösning?

def replace_periods_with_newlines(string_value):
    for character in string_value:
        if character == '.':
            character = '\n'
    return string_value

print(replace_periods_with_newlines("hej.hur mår du.jag mår bra!"))

hej.hur mår du.jag mår bra!

• Varför blir det ingen skillnad?

Den här då?

def replace_periods_with_newlines(string_value):
    i = 0
    while i < len(string_value):
        if string_value[i] == '.':
            string_value[i] = '\n'
        i += 1
    return string_value

print(replace_periods_with_newlines("hej.hur mår du.jag mår bra!"))

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[9], line 9
      6         i += 1
      7     return string_value
----> 9 print(replace_periods_with_newlines("hej.hur mår du.jag mår bra!"))

Cell In[9], line 5, in replace_periods_with_newlines(string_value)
      3 while i < len(string_value):
      4     if string_value[i] == '.':
----> 5         string_value[i] = '\n'
      6     i += 1
      7 return string_value

TypeError: 'str' object does not support item assignment

Vi var tvugna att använda en ackumulator

def replace_periods_with_newlines(string_value):
    result = ""
    for character in string_value:
        if character == '.':
            result += '\n'
        else:
            result += character
    return result

print(replace_periods_with_newlines("hej.hur mår du.jag mår bra!"))

hej
hur mår du
jag mår bra!

App, app, app! Vänta lite! Vi ändrar ju på result där! Har vi inte bara bytt vilket värde vi ändrar?

• Nästan. Vi har bytt ut värdet, inte ändrat det.
• Vad är skillnaden?

Vad är result?

Vad är en variabel över huvud taget?

Variabler som referenser till värden

• I de flesta fall är det enklast att se variabler som "etiketter" som refererar till värden.
• En tilldelningssats, t.ex. result = "", kan ses som att vi säger "låt etiketten result referera till värdet ..."

Vad gör vi egentligen med result?

def replace_periods_with_newlines(string_value):
    result = ""
    for character in string_value:
        if character == '.':
            result += '\n'
        else:
            result += character
    return result

print(replace_periods_with_newlines("hej.hur mår du.jag mår bra!"))

hej
hur mår du
jag mår bra!

• Vi ersätter värdet i result.
• Ett nytt sträng-objekt skapas varje iteration.
• result refererar nu till det nya objektet.

Föränderliga värden

• Av de datatyper som vi stött på så tillhör listor kategorin förändringsbara (eng. mutable) värden.
• Detta betyder att vi kan ändra på dessa värden.
• Vi kan t.ex. byta ut första elementet i listan [1, 2, 3] till 5

numbers = [1, 2, 3]
print(numbers)
numbers[0] = 5
print(numbers)

[1, 2, 3]
[5, 2, 3]

• Samma sak med sträng gav fel.

Jämförelse

numbers_list = [1, 2, 3]
print(numbers_list)
numbers_list[0] = 5
print(numbers_list)

[1, 2, 3]
[5, 2, 3]

numbers_string = "123"
print(numbers_string)
numbers_string[0] = "5"
print(numbers_string)

123

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[14], line 3
      1 numbers_string = "123"
      2 print(numbers_string)
----> 3 numbers_string[0] = "5"
      4 print(numbers_string)

TypeError: 'str' object does not support item assignment

Okej, så det blir runtime-fel, vad är problemet?

• Runtime fel är relativt lätta att fixa.
• Programmet kraschar och vi får ett felmeddelande. Enkelt.

Tillbaka till referenser

• Vi kan låta olika variabler referera till samma värde:

my_list = [1, 2, 3]
other_list = my_list
print(other_list)

Konsekvenser

my_list = [1, 2, 3]
other_list = my_list
my_string = "123"
other_string = my_string

print(f"{my_list=}")
print(f"{other_list=}")
print(f"{my_string=}")
print(f"{other_string=}")

my_list += [4]
my_string += "4"

print(f"{my_list=}")
print(f"{other_list=}")
print(f"{my_string=}")
print(f"{other_string=}")

Blir det alltid så?

my_list = [1, 2, 3]
other_list = my_list
my_string = "123"
other_string = my_string

print(f"{my_list=}")
print(f"{other_list=}")
print(f"{my_string=}")
print(f"{other_string=}")

my_list = my_list + [4]
my_string = my_string + "4"

print(f"{my_list=}")
print(f"{other_list=}")
print(f"{my_string=}")
print(f"{other_string=}")

• Nu blev det ju likadant!
• Det kluriga är augmented assignment för muterbara datatyper.

Kan vi göra det här lite mindre otydligt?

my_list = [1, 2, 3]
other_list = my_list

print(f"{my_list=}")
print(f"{other_list=}")

my_list=[1, 2, 3]
other_list=[1, 2, 3]

my_list.extend([4])

print(f"{my_list=}")
print(f"{other_list=}")

my_list=[1, 2, 3, 4]
other_list=[1, 2, 3, 4]

• Om vi använder extend så ändrar vi i objektet.
• Detsamma gäller för append.

Men om...

my_list = [1, 2, 3]
other_list = my_list

print(f"{my_list=}")
print(f"{other_list=}")

my_list=[1, 2, 3]
other_list=[1, 2, 3]

my_list = my_list + [4]

print(f"{my_list=}")
print(f"{other_list=}")

my_list=[1, 2, 3, 4]
other_list=[1, 2, 3]

• Använder vi +-operatorn får vi ett nytt objekt.

Så vad gör += för listor? Syntaktiskt socker för list.extend()

my_list = [1, 2, 3]
other_list = my_list

print(f"{my_list=}")
print(f"{other_list=}")

my_list=[1, 2, 3]
other_list=[1, 2, 3]

my_list += [4]

print(f"{my_list=}")
print(f"{other_list=}")

my_list=[1, 2, 3, 4]
other_list=[1, 2, 3, 4]

Vad händer när vi skickar föränderliga värden till funktioner?

def change_and_return_list(a_list):
    a_list.append("list was changed")
    return a_list

my_list = [1, 2, 3]
other_list = my_list
third_list = change_and_return_list(my_list)

print(my_list)
print(other_list)
print(third_list)

[1, 2, 3, 'list was changed']
[1, 2, 3, 'list was changed']
[1, 2, 3, 'list was changed']

Beror på vad funktionen gör!

def change_and_return_list(a_list):
    a_list = a_list + ["list was changed"]
    return a_list

my_list = [1, 2, 3]
other_list = my_list
third_list = change_and_return_list(my_list)

print(my_list)
print(other_list)
print(third_list)

[1, 2, 3]
[1, 2, 3]
[1, 2, 3, 'list was changed']

Sammanfattningsvis: Det är klurigt.

Förståelse och intuition kommer med övning.

• Det viktiga just nu är att komma ihåg att detta är en vanlig felkälla.

Okej, andas.

• Igen, det viktiga just nu är att komma ihåg att detta är en vanlig felkälla.

Ny datatyp: tuple

Som en lista, fast oföränderlig

Tuple

numbers_list = [1, 2, 3]
print(numbers_list)
numbers_list[0] = 5
print(numbers_list)

[1, 2, 3]
[5, 2, 3]

numbers_tuple = (1, 2, 3)
print(numbers_tuple)
numbers_tuple[0] = 5
print(numbers_tuple)

(1, 2, 3)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[26], line 3
      1 numbers_tuple = (1, 2, 3)
      2 print(numbers_tuple)
----> 3 numbers_tuple[0] = 5
      4 print(numbers_tuple)

TypeError: 'tuple' object does not support item assignment

• Men varför? Listor verkar så mycket mer flexibelt.
• Säkerhet. Ibland vill vi vara säkra på att ett objekt inte kan förändras.

Ny datatyp: dict

Nycklar associerade med värden

• En viktig anledning till att vi behöver ha koll på vilka datatyper som är muterbara och inte.

Dictionary

• Dictionary eller dict i Python.
  • Mer generellt: associationslista (eng. associative array, symbol table, map)
  • Kärt barn har många namn.
• Nyckel-värde-par
• Värden hämtas med hjälp av nyckel istället för index som i fallet med listor och tupler.
• Alla datatyper som är oföränderliga (immutable) kan användas som nycklar, t.ex. flyttal, heltal, strängar, tupler
• Alla datatyper kan vara värden

• "A Dictionary of the English Language" (1755) Samuel Johnson

Syntax

dict_example = {"key1": "value 1", 345: "value 2", 3: 54 }
print(dict_example[3])

54

dict_example["key1"] = "a new value" print(dict_example)

dict_example["the answer"] = 42 print(dict_example)

Iterera över en dict

• Punktnotation för att komma åt alla
  • nycklar: dict.keys()
  • värden: dict.values()
  • nyckel-värdepar: dict.items()
  • ("dict" refererar till ett värde av typen dictionary, denna notation används även i pythondokumentationen)
• Metoderna dict.keys(), dict.values() och dict.items() returnerar olika "vyer".
  • Vyer kan liknas vid listor.

Iterera över nycklar

dict_example = {"key1": "value 1", 345: "value 2", 3: 54 }
for key in dict_example.keys():
    print(key)
    

key1
345
3

Iterera över värden

dict_example = {"key1": "value 1", 345: "value 2", 3: 54 }
for key in dict_example.values():
    print(key)
    

value 1
value 2
54

Om vi vill ha både nycklar och värden då?

• Dåligt sätt:

dict_example = {"key1": "value 1", 345: "value 2", 3: 54 }
for key in dict_example.keys():
    print(key, ":", dict_example[key])
    

key1 : value 1
345 : value 2
3 : 54

• Väldigt vanligt, men inte rekommenderat.

Om vi vill ha både nycklar och värden då?

• Bättre sätt:

dict_example = {"key1": "value 1", 345: "value 2", 3: 54 }
for key, value in dict_example.items():
    print(key, ":", value)
    

key1 : value 1
345 : value 2
3 : 54

• Många gånger snabbare och mer "Pythonic"

Dataabstraktion

• Piet Mondrian
• Composition II in Red, Blue, and Yellow, 1930, Kunsthaus Zürich

Abstraktion

• programabstraktion: dela upp problem i delproblem, dela upp en funktion i flera funktioner
• dataabstraktion: koppla ihop och strukturera information

Dataabstraktion

# en variabel per värde
pokemon_name = "pidgey"
ability1 = "big-pecks"
ability2 = "tangled-feet"
ability3 = "keen-eye"

• Hur gör vi om vi vill ha information om fler eller färre "abilities" på ett smidigt sätt?

Dataabstraktion

pokemon_name = "pidgey"
# listor kan användas för att lagra 0 eller fler värden
abilities = ["big-pecks", "tangled-feet", "keen-eye"]

• Listor kan användas för information som kan innehålla fler än ett värde.
• Hur gör vi om vi vill ha information om flera pokemons? Ska vi ha pokemon_name1, pokemon_name2, abilities1, abilities2?

Dataabstraktion

pokemon1 = ["pidgey", ["big-pecks", "tangled-feet", "keen-eye"]]
pokemon2 = ["ditto", ["imposter", "limber"]]

• Vi kan samla ihop informationen om varje pokemon till en lista samt bestämma den ordning som informationen ska komma i.

Dataabstraktion

pokemon = [ ["pidgey", ["big-pecks", "tangled-feet", "keen-eye"]],
            ["ditto", ["imposter", "limber"]] ]

• Vi kan också samla ihop alla pokemon-listor i en lista.

Dataabstraktion

pokemon = [ { "name": "pidgey",
              "abilities": ["big-pecks", "tangled-feet", "keen-eye"] },
            { "name": "ditto",
              "abilities": ["imposter", "limber"] } ]

• Vi hade även kunnat använda ett dictionary för att representera en Pokémon.

Dataabstraktion

pokemon = {"pidgey": { "name": "pidgey",
                       "abilities": ["big-pecks", "tangled-feet", "keen-eye"] },
           "ditto": { "name": "ditto",
                      "abilities": ["imposter", "limber"] }}

• Här har vi istället för en lista använt ett dictionary som har namnen på pokemons som nyckel och dictionaryt med all pokemon-information som värde.

• Redundant att ha namn som nyckel och sen en inre dict med samma namn som värde.
• Kanske, men i många fall har vi ett kortnamn och ett fullständigt namn.

Dataabstraktion

pokemon = {"johsj47": { "name": "johan falkenjack",
                        "abilities": ["insomnia", "oblivious", "gluttony"] } }

• Här har vi istället för en lista använt ett dictionary som har namnen på pokemons som nyckel och dictionaryt med all pokemon-information som värde.

• Här har vi ett extra fiktivt exempel med ett användarnamn och ett fullständigt namn

Abstrakta datatyper (ADT)

• "Programming with abstract data types" (1974). Barbara Liskov & Stephen Zilles.
• Abstrakt datatyp
  • datastruktur baserad på någon mer primitiv datatyp, t.ex. en lista
  • funktioner som används på dessa datastrukturer
  • poängen är att abstrahera bort onödig komplexitet
• Föregångare till en objektorienterad approach.
• Vi har redan pratat om en ADT: Stack.

Exempel på abstrakt datatyp

• Kö (eng. queue)
  • lista med element är kön, index 0 är nästa på tur
  • funktionen create_empty_queue() som returnerar en tom kö
  • funktionen enqueue(value, queue) som lägger till värdet value till slutet på kön queue
  • funktionen dequeue(queue) som returnerar värdet som är först i kön och plockar även bort det från kön

• Stack är LIFO - last in, first out
• Queue är FIFO - first in, first out

(Jätte)enkel kö i Python

def create_empty_queue():
    return []

def enqueue(value, queue):
    queue.append(value)

def dequeue(queue):
    return queue.pop(0)

q = create_empty_queue()
print(1, q)
enqueue('a', q)
print(2, q)
enqueue('b', q)
print(3, q)
print(4, f"{dequeue(q)=}")
print(5, q)
enqueue('c', q)
print(6, q)

1 []
2 ['a']
3 ['a', 'b']
4 dequeue(q)='a'
5 ['b']
6 ['b', 'c']

print(7, f"{dequeue(q)=}")
print(8, f"{dequeue(q)=}")
print(9, f"{dequeue(q)=}")

7 dequeue(q)='b'
8 dequeue(q)='c'

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
Cell In[37], line 3
      1 print(7, f"{dequeue(q)=}")
      2 print(8, f"{dequeue(q)=}")
----> 3 print(9, f"{dequeue(q)=}")

Cell In[36], line 8, in dequeue(queue)
      7 def dequeue(queue):
----> 8     return queue.pop(0)

IndexError: pop from empty list

• Väldigt enkel, helt upp till oss att hålla reda på att q faktiskt är en kö.
• Det är bara en kö för att vi använder det som en kö, egentligen bara en vanlig lista.
• Ingen felhantering.

(Pytte)lite mer avancerad kö i Python

def create_empty_queue():
    return ('queue', [])

def enqueue(value, queue):
    if queue[0] == 'queue':
        queue[1].append(value)
    else:
        raise TypeError("Not a queue")

def dequeue(queue):
    if queue[0] == 'queue':
        if queue[1]:
            return queue[1].pop(0)
        else:
            return None
    else:
        raise TypeError("Not a queue")
    

• Här har vi valt att explicit säga att en kö är en 2-tupel där första elementet är en identifierare, strängen "queue".
• Eftersom varken en tupel eller en sträng är muterbar vet vi att detta aldrig ändras.

(Pytte)lite mer avancerad kö i Python

q = create_empty_queue()
print(1, q)
enqueue('a', q)
print(2, q)
enqueue('b', q)
print(3, q)
print(4, f"{dequeue(q)=}")
print(5, q)
enqueue('c', q)
print(6, q)

1 ('queue', [])
2 ('queue', ['a'])
3 ('queue', ['a', 'b'])
4 dequeue(q)='a'
5 ('queue', ['b'])
6 ('queue', ['b', 'c'])

print(7, f"{dequeue(q)=}")
print(8, f"{dequeue(q)=}")
print(9, f"{dequeue(q)=}")

7 dequeue(q)='b'
8 dequeue(q)='c'
9 dequeue(q)=None

• Här har vi valt att explicit säga att en kö är en 2-tupel där första elementet är en identifierare, strängen "queue".
• Eftersom varken en tupel eller en sträng är muterbar vet vi att detta aldrig ändras.

Stop! Tupler var ju inte muterbara!

• Listan på index 0 kan vi däremot ändra i. Inte byta ut (det skulle innebära att tupeln ändrades), men modifiera.

Hur ser vår datastruktur ut?

q = create_empty_queue()

Hur ser vår datastruktur ut?

q = create_empty_queue()

Hur ser vår datastruktur ut?

q = create_empty_queue()
enqueue('a', q)

Hur ser vår datastruktur ut?

q = create_empty_queue()
enqueue('a', q)
enqueue('b', q)

Hur ser vår datastruktur ut?

q = create_empty_queue()
enqueue('a', q)
enqueue('b', q)
print(f"{dequeue(q)=}")

dequeue(q)='a'

Hur ser vår datastruktur ut?

q = create_empty_queue()
enqueue('a', q)
enqueue('b', q)
dequeue(q)
enqueue('c', q)

Vi kan inte lägga till, ta bort, eller byta ut ett element i en tupel.

Men om elementet i sig är muterbart, så kan vi ändra på det.

Bearbetning av nästlade datastrukturer

Nästlade datastrukturer

• $A$ är en nästlad datastruktur om
  • $A$ innehåller flera värden
  • Ett av värdena i $A$ i sin tur innehåller flera värden

list_of_lists = [["Ada Lovelace", 1815], ["Joan Clarke", 1917]]
list_of_dicts = [ { "name": "Ada Lovelace", "birthyear": 1815 }, { "name": "Joan Clarke", "birthyear": 1815 } ]
dict_with_some_list_value = { "name": "ditto", "abilities": ["imposter", "limber"] }

Hur kommer vi åt nästlade värden?

lista1 = [["a", "b", "c"], ["d", "e", "f"]]

# första elementet i lista1
print(f"{lista1[0]=}")

# första elementet i första elementet i lista1
print(f"{lista1[0][0]=}")

# andra elementet i första elementet i lista1
print(f"{lista1[1][1]=}")

lista1[0]=['a', 'b', 'c']
lista1[0][0]='a'
lista1[1][1]='e'

Hur kommer vi åt nästlade värden?

dict1 = { "frukter": ["a", "b", "c"], 
          "bilar": ["d", "e", "f"] }

# värdet associerat med nyckeln "frukter"
print(f"{dict1['frukter']=}")

# första elementet i listan associerad med nyckeln "frukter"
print(f"{dict1['frukter'][0]=}")

# andra elementet i listan associerad med nyckeln "frukter"
print(f"{dict1['frukter'][1]=}")

dict1['frukter']=['a', 'b', 'c']
dict1['frukter'][0]='a'
dict1['frukter'][1]='b'

En nästlad loop för att bearbeta en nästlad datastruktur

outer_list = [ ["a", "b", "c"], ["d", "e", "f", "g"] ]

# om vi för varje inre lista i outer_list vill skriva ut den inre listans element?
outer_index = 0
while outer_index < len(outer_list):
    inner_list = outer_list[outer_index]
    # kod som skriver ut varje element i inner_list
    inner_index = 0
    while inner_index < len(inner_list):
        print(inner_list[inner_index])
        inner_index += 1
    outer_index += 1

a
b
c
d
e
f
g

Gaaaaah... index.

Vi har faktiskt någon typ av sekvenser... for!

outer_list = [ ["a", "b", "c"], ["d", "e", "f", "g"] ]

# om vi för varje inre lista i outer_list vill skriva ut den inre listans element?
for outer_element in outer_list:
    # kod som skriver ut varje element i inner_list
    for inner_element in outer_element:
        print(inner_element)

a
b
c
d
e
f
g

Nästlade strukturer med dictionaries

Bearbeta lista av dictionaries 1

pokemons = [ { "name": "bulbasaur", "abilities": ["chlorophyll", "overgrow"] },
             { "name": "squirtle", "abilities": ["rain-dish", "torrent"] } ]

def print_dictionaries(list_of_dictionaries):
    # gå igenom listan med dictionaries
    for dictionary in list_of_dictionaries:
        # gå igenom alla nycklar i aktuellt dictionary
        for key in dictionary.keys():
            print(f"The key {key} has the value: {dictionary[key]}")

print("pokemons:")
print_dictionaries(pokemons)

pokemons:
The key name has the value: bulbasaur
The key abilities has the value: ['chlorophyll', 'overgrow']
The key name has the value: squirtle
The key abilities has the value: ['rain-dish', 'torrent']

Bearbeta lista av dictionaries 1

books = [ { "title": "Introduction to Python", "pages": 314 },
          { "title": "Another introduction to Python", "pages": 413 } ]


print("books:")
print_dictionaries(books)

books:
The key title has the value: Introduction to Python
The key pages has the value: 314
The key title has the value: Another introduction to Python
The key pages has the value: 413

Bearbeta lista av dictionaries 2

def print_dictionaries(list_of_dictionaries):
    
    # gå igenom listan med dictionaries
    for dictionary in list_of_dictionaries:
        
        # gå igenom alla nycklar i varje dictionary
        for key in dictionary:
            
            # i de fall som värdet för en nyckel är en lista
            if type(dictionary[key]) == list:
                print(f"Value of key {key} is a list:")
                
                # skriv ut varje värde i listan dictionary[key]
                for value in dictionary[key]:
                    print(f"- {value}")
                    
            # när värdet i dictionaryt inte är en lista
            else:
                print(f"The key {key} has the value: {dictionary[key]}")

Bearbeta lista av dictionaries 2

print("pokemons:")
print_dictionaries(pokemons)
print("\nbooks:")
print_dictionaries(books)

pokemons:
The key name has the value: bulbasaur
Value of key abilities is a list:
- chlorophyll
- overgrow
The key name has the value: squirtle
Value of key abilities is a list:
- rain-dish
- torrent

books:
The key title has the value: Introduction to Python
The key pages has the value: 314
The key title has the value: Another introduction to Python
The key pages has the value: 413

Leta efter värde i nästlad lista

blandad_lista = [ "a", ["b", "c"], "d", "e", ["f", "g"] ]
def look_for_value(needle, haystack):
    # bearbeta yttre listan
    for value in haystack:
        # bearbetning av yttre värden som är listor
        if type(value) == list:
            for inner_value in value:
                if inner_value == needle:
                    return True
        # om yttre värde inte är en lista, kolla om det är det vi letar efter
        elif value == needle:
            return True
    return False

look_for_value("c", blandad_lista)

True

Okej, men om vi inte vet exakt hur strukturen kommer se ut i förväg?

Om vi måste kunna hantera godtyckligt många nivåer av nästling?

• Jag ser några som skruvar nervöst på sig. Ni vet var vi är på väg?

Rekursion

Rekursion

• Självlikhet eller självreferens.
• Fenomen som i sin struktur innehåller en mindre variant av sig själva.
  • Träd, med grenar, som har grenar, som har grenar...
  • Världskarta, som består av kartor över länder, som innehåller kartor över städer, som innehåller kartor över kvarter...
  • En mening kan innehålla en bisats, som kan innehålla en bisats, som kan innehålla en bisats...
• Processer som innehåller sig själva som ett delsteg.
  • Surdeg, där den viktigaste ingrediensen är? Surdeg.
  • Att gå upp för en trappa med $n$ steg, som består av att först gå upp för en trappa med $1$ trappsteg...

• Vilka har hört talas om rekursion förut?
• I vilket sammanhang?

Droste-effekten

Källa: https://xkcd.com/2891

• Randall Munroe var vänlig nog att publicera den här bilden i sin webcomic xkcd så sent som i onsdags förra veckan.
• Logaritmisk spiral enligt gyllene snittet.
• Sidan på varje kvadrat är ekvivalent med Fibonacci-serien, men mer om det i Pythonuppgift 3.3.

"Memeception" - en vanlig misstolkning

• Filmen Inception handlade till stor del om rekursion (drömmar i drömmar), och memes som innehöll exempel på rekursion använde ofta suffixet "-ception" som en referens till filmen. Ordet "inception" har i sig inget med rekursion att göra.

Side note, när vi ändå pratar om vanliga misstolkningar ;)

kodkommentar $\neq$ hashtag

• Tecknet # kallas, bland annat, för hash (också number sign, pound sign, brädhög, brädgård, gärdsgård, stege, staket, spjälstaket, fyrkant, vedstapel, haga, stockhög, grind, fyrtagg).
• En hashtag är en metadatatag som indikerats med ett hashtecken.
  • Vanligt i sociala medier för att ange etiketter, nyckelord, teman, etc.
  • Andra tag-system förekommer med olika formalismer i olika sammanhang, t.ex. @-tags för att tagga en viss användare är också vanligt i sociala medier.
• En kodkommentar (i Python och många andra programmeringsspråk) är en text som följer efter ett hashtecken och som ignoreras av Pythontolken.

En sista rekursiv bild

Okej, en till...

Vad har detta med programmering att göra?

• Rekursiva datastrukturer.
  • T.ex. listor som kan innehålla listor, som kan innehålla listor, som kan...
  • Grafer, där varje möjlig delgraf i sig är en graf.
    • T.ex. använder vi ofta grafer för att representera kartor.

• Rekursiva processer.
  • Funktioner som direkt anropar sig själva.
  • Funktioner som i en ändlig kedja av funktionsanrop anropar sig själva, t.ex. funktion $A$ anropar funktion $B$ och funktion $B$ i sin tur anropar $A$.

Komponenter i en enkel rekursiv funktion

def rec_fun(input):
    if *stoppvillkor*:
        return *trivialt basfall*
    else:
        return do_something(input) *kombinerat med* rec_fun(*ett värde härlett från input*)

• Inte en speciell syntax, bara ett generellt mönster.
• Vad gör denna enkel? Bara en klausul med rekursivt anrop. Vi kan ha fler.

Summera en lista av heltal med for-loop

• Vi vill summera listan [1, 2, 75, 6, 7]

def sum_list_for(values):
    result = 0
    for value in values:
        result += value
    return result

print(f"{sum_list_for([1, 2, 75, 6, 7])=}")

sum_list_for([1, 2, 75, 6, 7])=91

Summera en lista av heltal med rekursion

• Vi vill summera listan [1, 2, 75, 6, 7]

def sum_list_rec(values):
    if values == []:
        return 0
    else:
        return values[0] + sum_list_rec(values[1:])

print(f"{sum_list_rec([1, 2, 75, 6, 7])=}")

sum_list_rec([1, 2, 75, 6, 7])=91

• Stoppvillkor och trivialt basfall.
• Var är do_something?
• Kombinationsoperation.
• Rekursionssteg.

Jaha, men hur kom vi på det då?

Rekursiv problemlösning

• För att lösa ett problem rekursivt, behöver vi formulera eller dela upp det på ett sådant sätt så att delarna är enklare varianter av det större problemet.

• Om vi har problemet summera talen 1, 2, 75, 6 och 7. Att uttrycka det som 1 + 2 + 75 + 6 + 7 är att försöka lösa allt på en gång.
• Ett alternativt sätt är uttrycka det som 1 + summan av de resterande talen; 2, 75, 6, 7
• Summan av de resterande talen i sin tur kan vi uttrycka på samma sätt, 2 + summan av de resterande talen; 75, 6, 7
• Vi har hittat ett sätt att formulera problemet så att vi kan tillämpa samma lösning på mindre och mindre varianter av samma problem.

Ett första försök

def sum_list_rec(values):
    return values[0] + sum_list_rec(values[1:])

print(f"{sum_list_rec([1, 2, 75, 6, 7])=}")

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
Cell In[62], line 4
      1 def sum_list_rec(values):
      2     return values[0] + sum_list_rec(values[1:])
----> 4 print(f"{sum_list_rec([1, 2, 75, 6, 7])=}")

Cell In[62], line 2, in sum_list_rec(values)
      1 def sum_list_rec(values):
----> 2     return values[0] + sum_list_rec(values[1:])

Cell In[62], line 2, in sum_list_rec(values)
      1 def sum_list_rec(values):
----> 2     return values[0] + sum_list_rec(values[1:])

    [... skipping similar frames: sum_list_rec at line 2 (3 times)]

Cell In[62], line 2, in sum_list_rec(values)
      1 def sum_list_rec(values):
----> 2     return values[0] + sum_list_rec(values[1:])

IndexError: list index out of range

• Vad har vi glömt?

Ett första försök - fel när values == []

• Vad bör anropet sum_list_rec([]) bli?

• Vad är summan av alla tal i en tom lista?
• Vad kan vi lägga till för att hantera det fallet?

Summera en lista av heltal med rekursion

• Vi vill summera listan [1, 2, 75, 6, 7]

def sum_list_rec(values):
    if values == []:
        return 0
    else:
        print(f"return {values[0]} + sum_list_rec({values[1:]})")
        return values[0] + sum_list_rec(values[1:])

print(f"{sum_list_rec([1, 2, 75, 6, 7])=}")

return 1 + sum_list_rec([2, 75, 6, 7])
return 2 + sum_list_rec([75, 6, 7])
return 75 + sum_list_rec([6, 7])
return 6 + sum_list_rec([7])
return 7 + sum_list_rec([])
sum_list_rec([1, 2, 75, 6, 7])=91

• Stoppvillkor och trivialt basfall.
• Var är do_something?
• Kombinationsoperation.
• Rekursionssteg.

Mönster för att skriva en rekursiv funktion

• Vi letar efter det "enklaste" fallet av problemet som ska lösas, basfallet.
  • Basfallet är det problemfall som är så enkelt att svaret är givet.
• Basfallet följs sedan av ett eller flera rekursiva anrop på en "enklare" variant av ursprungsproblemet.
• Se till att alla return-satser returnerar värde av samma datatyp.

Nytt problem: summan av alla tal från $0$ till $n$?

• Vad är summan av alla tal från $0$ till $n$?
  • Summan av alla tal från $n$ till $0$?

• Vad är summan av alla tal från $n$ till $0$?
  • $n$ $+$ summan av alla tal från $(n-1)$ till $0$

• Vad är summan av alla tal från $(n-1)$ till $0$?
  • $(n-1)$ $+$ summan av alla tal från $(n-2)$ till $0$
• osv ...

Iterativ summa från $0$ till $n$

def sum_0_to(n):
    result = 0
    for i in range(n+1):
        result += i
    return result
    
    
print(f"{sum_0_to(100)=}")

sum_0_to(100)=5050

Rekursiv summa från $0$ till $n$

def sum_0_to(n):
    if n == 0:
        return 0
    else:
        return n + sum_0_to(n-1)
    
print(f"{sum_0_to(100)=}")

sum_0_to(100)=5050

• Vi vet att det finns bättre och enklare lösningar på detta.
• Gauss metod för aritmetiska serier löser detta utan vare sig iteration eller rekursion.

Är rekursion verkligen nödvändigt?

• Tekniskt sett... nej.
• Church-Turing-satsen, som bevisade att den Universella Turing-maskinen är ekvivalent med $\lambda$-kalkylen, innebär också att alla rekursiva funktioner kan skrivas om till iterativa funktioner, och vice versa.
  • En kurs i programmeringsteori kan vara lämplig för den nyfikne.

Är rekursion alltid "krångligare" än iteration?

• Smaksak och vanesak.
• Vissa problem är till sin natur rekursiva och väldigt krångliga att lösa med iteration.
  • Problem som kan brytas ner i mindre likadana delar löses ofta enklare och mer lättläst med rekursion än med iteration.
• Rekursion har stor betydelse inom språkbehandling, artificiell intelligens, databehandling, visualisering, etc.
• Varför började vi ens prata om rekursion?
  • Rekursion lämpar sig särskilt bra för att hantera nästlade datastrukturer.

Rekursion för nästlade datastrukturer

Exempel: Trädrekursion

Platt lista som trädstruktur

• [ 1, 2, 3]
• Problem: Vad är summan av alla löv?
• Alla noder är löv, dvs alla noder har värden.
• Vi anropar sum_rec([ 1, 2, 3])

def sum_rec(values):
    if not values:
        return 0
    else:
        return values[0] + sum_rec(values[1:])

Platt lista som trädstruktur

• [ 1, 2, 3]
• Problem: Vad är summan av alla löv?
• Noden är ett löv.
• Beräkna 1 + summan av övriga värden.
  • sum_rec anropas med resten av listan som argument:
  • sum_rec([ 2, 3])

def sum_rec(values):
    if not values:
        return 0
    else:
        return values[0] + sum_rec(values[1:])

Platt lista som trädstruktur

• [ 2, 3]
• Problem: Vad är summan av alla löv?
• Alla noder är löv, dvs alla noder har värden.

def sum_rec(values):
    if not values:
        return 0
    else:
        return values[0] + sum_rec(values[1:])

Platt lista som trädstruktur

• [ 2, 3]
• Problem: Vad är summan av alla löv?
• Noden är ett löv.
• Beräkna 2 + summan av övriga värden.
  • sum_rec anropas med resten av listan som argument:
  • sum_rec([ 3])

def sum_rec(values):
    if not values:
        return 0
    else:
        return values[0] + sum_rec(values[1:])

Platt lista som trädstruktur

• [ 3]
• Problem: Vad är summan av alla löv?
• Alla noder är löv, dvs alla noder har värden.

def sum_rec(values):
    if not values:
        return 0
    else:
        return values[0] + sum_rec(values[1:])

Platt lista som trädstruktur

• [ 3]
• Problem: Vad är summan av alla löv?
• Noden är ett löv.
• Beräkna 3 + summan av övriga värden.
  • sum_rec anropas med resten av listan som argument:
  • sum_rec([ ])

def sum_rec(values):
    if not values:
        return 0
    else:
        return values[0] + sum_rec(values[1:])

Platt lista som trädstruktur

• [ ]
• Problem: Vad är summan av alla löv?
• Inga noder finns.
• Summan av inga värden är 0 så vi returnerar 0.

def sum_rec(values):
    if not values:
        return 0
    else:
        return values[0] + sum_rec(values[1:])

Platt lista som trädstruktur

• [ 3]
• Problem: Vad är summan av alla löv?
• Summan är värdet på detta löv, 3, + summan av övriga värden, vilket nu har beräknats till 0.

def sum_rec(values):
    if not values:
        return 0
    else:
        return values[0] + sum_rec(values[1:])

Platt lista som trädstruktur

• [ 3]
• Problem: Vad är summan av alla löv?
• Returnera summan, dvs 3.

def sum_rec(values):
    if not values:
        return 0
    else:
        return values[0] + sum_rec(values[1:])

Platt lista som trädstruktur

• [ 2, 3]
• Problem: Vad är summan av alla löv?
• Summan är värdet på detta löv, 2, + summan av övriga värden, vilket nu har beräknats till 3.

def sum_rec(values):
    if not values:
        return 0
    else:
        return values[0] + sum_rec(values[1:])

Platt lista som trädstruktur

• [ 2, 3]
• Problem: Vad är summan av alla löv?
• Summan är värdet på detta löv, 2, + summan av övriga värden, vilket nu har beräknats till 3.

def sum_rec(values):
    if not values:
        return 0
    else:
        return values[0] + sum_rec(values[1:])

Platt lista som trädstruktur

• [ 2, 3]
• Problem: Vad är summan av alla löv?
• Returnera summan, dvs 5.

def sum_rec(values):
    if not values:
        return 0
    else:
        return values[0] + sum_rec(values[1:])

Platt lista som trädstruktur

• [ 1, 2, 3]
• Problem: Vad är summan av alla löv?
• Summan är värdet på detta löv, 1 + summan av övriga värden, vilket nu har beräknats till 5.

def sum_rec(values):
    if not values:
        return 0
    else:
        return values[0] + sum_rec(values[1:])

Platt lista som trädstruktur

• [ 1, 2, 3]
• Problem: Vad är summan av alla löv?
• Summan är värdet på detta löv, 1 + summan av övriga värden, vilket nu har beräknats till 5.

def sum_rec(values):
    if not values:
        return 0
    else:
        return values[0] + sum_rec(values[1:])

Platt lista som trädstruktur

• [ 1, 2, 3]
• Problem: Vad är summan av alla löv?
• Returnera summan, dvs 6.

def sum_rec(values):
    if not values:
        return 0
    else:
        return values[0] + sum_rec(values[1:])

Nästlade strukturer kan ses som trädstrukturer

• [1, [2, 3], [ [4, 5], 6 ] ]
• Problem: Vad är summan av alla löv?
• Om nod inte är ett löv:
  • Noden är ett delträd, beräkna summan av delträdet.
  • (Summan av ett delträd är beräknas på samma sätt som summan av ett träd.)

Nästlade strukturer kan ses som trädstrukturer

def sum_rec_nest(values):
    # om vi inte har några värden är summan 0
    if not values:
        return 0
     # om noden inte är ett värde, räkna ut delträdets värde och addera det till
     # resten av värdena
    elif type(values[0]) == list:
        return sum_rec_nest(values[0]) + sum_rec_nest(values[1:])
     # noden är ett löv, addera dess värde till resten av värdena i trädet
    else:
        return values[0] + sum_rec_nest(values[1:])

sum_rec_nest([1, 2, 3])

6

sum_rec_nest([1, [2, 3], [[4, 5], 6]])

21

sum_rec_nest([1, [2, 3], [[4, 5, [6, 7, [8]]], 9]])

45

Nästlade strukturer kan ses som trädstrukturer

• [1, [2, 3], [ [4, 5], 6 ] ]
• Problem: Vad är summan av alla löv?
• Noden är ett löv: Beräkna 1 + summan av resten
  • sum_rec_nest anropas på resten av listan:
  • sum_rec_nest([ [2, 3], [ [4, 5], 6 ] ])

Nästlade strukturer kan ses som trädstrukturer

• [ [2, 3], [ [4, 5], 6 ] ]
• Problem: Vad är summan av alla löv?

Nästlade strukturer kan ses som trädstrukturer

• [ [2, 3], [ [4, 5], 6 ] ]
• Problem: Vad är summan av alla löv?
• Noden är ett delträd: Beräkna summan av delträdet + summan av resten
  • sum_rec_nest anropas på första noden:
  • sum_rec_nest([2, 3])

Nästlade strukturer kan ses som trädstrukturer

• [2, 3]
• Problem: Vad är summan av alla löv?

Nästlade strukturer kan ses som trädstrukturer

• [ [2, 3] ]
• Problem: Vad är summan av alla löv?
• Beräkna summan av delträdet.

Nästlade strukturer kan ses som trädstrukturer

• [ [2, 3] ]
• Problem: Vad är summan av alla löv?
• Returnera summan, dvs 5.

Nästlade strukturer kan ses som trädstrukturer

• [ [2, 3], [ [4, 5], 6 ] ]
• Problem: Vad är summan av alla löv?
• Summan av första noden är 5: Beräkna 5 + summan av resten
  • sum_rec_nest anropas på resten av listan:
  • sum_rec_nest([ [ [4, 5], 6 ] ])

Nästlade strukturer kan ses som trädstrukturer

• [ [ [4, 5], 6 ] ]
• Problem: Vad är summan av alla löv?

Nästlade strukturer kan ses som trädstrukturer

• [ [ [4, 5], 6 ] ]
• Problem: Vad är summan av alla löv?
• Noden är ett delträd: Beräkna summan av delträdet + summan av resten
  • sum_rec_nest anropas på första noden:
  • sum_rec_nest([ [4, 5], 6 ])

Nästlade strukturer kan ses som trädstrukturer

• [ [4, 5], 6 ]
• Problem: Vad är summan av alla löv?

Nästlade strukturer kan ses som trädstrukturer

• [ [4, 5], 6 ]

• Problem: Vad är summan av alla löv?

• Noden är ett delträd: Beräkna summan av delträdet + summan av resten

  • sum_rec_nest anropas på första noden:
  • sum_rec_nest([4, 5])

Nästlade strukturer kan ses som trädstrukturer

• [4, 5]
• Problem: Vad är summan av alla löv?

Nästlade strukturer kan ses som trädstrukturer

• [4, 5]
• Problem: Vad är summan av alla löv?
• Returnera summan, dvs 9

Nästlade strukturer kan ses som trädstrukturer

• [ [4, 5], 6 ]

• Problem: Vad är summan av alla löv?

• Summan av första noden är 9: Beräkna 9 + summan av resten

  • sum_rec_nest anropas på resten av listan:
  • sum_rec_nest([ 6 ]) → 6

Nästlade strukturer kan ses som trädstrukturer

• [ [4, 5], 6 ]
• Problem: Vad är summan av alla löv?
• Returnera summan, dvs 15

Nästlade strukturer kan ses som trädstrukturer

• [ [ [4, 5], 6 ] ]
• Problem: Vad är summan av alla löv?
• Summan har beräknats till 15
• Returnera summan, dvs 15

Nästlade strukturer kan ses som trädstrukturer

• [ [2, 3], [ [4, 5], 6 ] ]
• Problem: Vad är summan av alla löv?
• Summan av första noden är beräknad till 5
• Summan av resten är beräknad till 15

Nästlade strukturer kan ses som trädstrukturer

• [ [2, 3], [ [4, 5], 6 ] ]
• Problem: Vad är summan av alla löv?
• Returnera summan, dvs 5 + 15

Nästlade strukturer kan ses som trädstrukturer

• [1, [2, 3], [ [4, 5], 6 ] ]
• Problem: Vad är summan av alla löv?
• Summan av resten har beräknats till 20

Nästlade strukturer kan ses som trädstrukturer

• [1, [2, 3], [ [4, 5], 6 ] ]
• Problem: Vad är summan av alla löv?
• Returnera summan, dvs 21

Leta efter ett värde i en nästlad lista

def look_for_value_rec_all(value, values):
    # Inget värde kan finnas i en tom lista
    if not values:
        return False
    
    # om första värdet inte är en lista, kolla om det är det värde
    # vi letar efter, returnera i så fall True
    elif values[0] == value:
        return True
    
    # om första värdet är en lista, returnera resultatet av att
    # leta i både den listan och resten av values
    elif type(values[0]) == list:
        return (look_for_value_rec_all(value, values[0]) or
                look_for_value_rec_all(value, values[1:]))

    # om inte första värdet varken var en lista eller det vi letade efter
    # returnera resultatet av att leta efter värdet i resten av listan
    else:
        return look_for_value_rec_all(value, values[1:])

Tillämpning av rekursion:

grafsökning

Rekursiva funktioner kan "utforska" flera olika lösningsvägar med trädrekursion

• Exempel: En karta med enkelriktade vägar representeras som en graf.
• Problem: Givet en startpunkt A kan vi ta oss till platsen B? Returnera vägen.
• Representation: Vi representerar grafen som ett dictionary där nycklarna är noder vars värde är en lista med de noder vi kan nå.

map1 = {"a": ["b", "c"],
 "b": [],
 "c": ["d"],
 "d": ["a"],
 "e": ["b"]}

Hitta vägen

def get_path(s_node, e_node, a_map, visited):
    """Returnera en lista med vägen från s_node till e_node om sådan finns."""
    # är e_node direkt tillgänglig?
    if e_node in a_map[s_node]:
        return visited + [s_node, e_node]
    # kolla om vi kan ta oss till e_node från någon av grannarna till s_node
    return get_path_hlp(a_map[s_node], e_node, a_map, visited + [s_node])

def get_path_hlp(s_nodes, e_node, a_map, visited):
    """Returnera den första vägen från en nod i s_nodes till e_node om sådan finns."""
    # om s_nodes är tom så kan vi inte ta oss till e_node
    if not s_nodes:
        return []
    # om vi inte redan besökt s_nodes[0]
    elif s_nodes[0] not in visited:
        # kolla om vi kan ta oss till e_node därifrån eller någon av de övriga
        # nodern i s_nodes
        path = get_path(s_nodes[0], e_node, a_map, visited)
        if path:
            return path
        else:
            return get_path_hlp(s_nodes[1:], e_node, a_map, visited)
    # om vi redan besökt s_nodes[0]
    else:
        # kolla om vi kan ta oss till e_node från någon av de övriga noderna
        # i s_nodes
        return get_path_hlp(s_nodes[2:], e_node, a_map, visited)

print(get_path('c', 'b', map1, []))

['c', 'd', 'a', 'b']

Hitta vägen (med for-loop)

Ibland är den bästa lösningen att kombinera rekursion med vanliga loop-konstruktioner.

def get_path_with_for(s_node, e_node, a_map, visited):
    """Returnera en lista med vägen från s_node till e_node om sådan finns."""
    # är e_node direkt tillgänglig?
    if e_node in a_map[s_node]:
        return visited + [s_node, e_node]
    # kolla om vi kan ta oss till e_node från någon av grannarna till s_node
    for next_node in a_map[s_node]:
        if next_node not in visited:
            path = get_path_with_for(next_node, e_node, a_map, visited + [s_node])
            if path:
                return path
    # om vi kommer hit kunde vi inte hitta någon väg
    return []

print(get_path_with_for('c', 'b', map1, []))

['c', 'd', 'a', 'b']

• Notera att vi fortfarande har en rekursiv funktion, men genom att använda en loop för den "platta" delen av problemet har vi fått det bästa av båda världar.

Större karta

map2 = {"a": ["d"],
        "b": ["e", "g"],
        "c": ["e", "h"],
        "d": ["g"],
        "e": ["d"],
        "f": ["g", "h"],
        "g": [],
        "h": ["e", "i"],
        "i": ["f"]}

print(get_path_with_for('h', 'g', map2, []))

['h', 'e', 'd', 'g']