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!")
        

• 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 while när for finns?

• För att kunna använda for krävs en sekvens.
• Exempel: Vi vill slå en 6-sidig tärning tills summan är minst 20.
  • Vi använder modulen random för att slumpa ett tal mellan 1 och 6 som representerar ett tärningsslag.
  • Variabeln total utgör både kontrollvariabel och ackumulatorvariabel, dvs. en variabel vars värde ackumuleras medan loopen utförs.

import random
total = 0

while total < 20:
    roll = random.randint(1, 6)
    total += roll
    print("Roll is:", roll, "( total is:", total, ")\n")

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:

Välj beskrivande variabelnamn...

i = ""
while i != 'q':
    i = input("Skriv något: ")
    p = None
    h = False
    for c in i:
        if p and p == c:
            h = True
        p = c
    if h:
        print("Det du skrev har upprepade bokstäver i sig!")
    else:
        print("Det finns inga upprepade bokstäver där.")
print("Hej då.")

Välj beskrivande variabelnamn...

user_input = ""
while user_input != 'q':
    user_input = input("Skriv något: ")
    prev_char = None
    has_repeated = False
    for curr_char in user_input:
        if prev_char and prev_char == curr_char:
            has_repeated = True
        prev_char = curr_char
    if has_repeated:
        print("Det du skrev har upprepade bokstäver i sig!")
    else:
        print("Det finns inga upprepade bokstäver där.")
print("Hej då.")

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
• 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"
print(f"Hej {namn}!")

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

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=}")

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

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

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!"))

• 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!"))

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!"))

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

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 ..."
• Vår tidigare liknelse med variabler som lådor som innehåller värden är alltså inte riktigt korrekt.

Variabler är inte lådor med värden i

• Man säger ofta lite slarvigt att en variabel "innehåller" ett värde, och illustrerar det med att variabeln är en låda som man stoppar ett värde i.
  • (T.ex. beskrev jag det så i kursens första föreläsning.)
• Det är mer korrekt (i Python) att säga att en variabel innehåller en referens till ett värde.
• Flera variabler kan referera till samma värde, dvs till samma stycke data i minnet.
• Vi kan byta ut vilket värde som referensen refererar till, dvs vilket stycke data i minnet som som pekas ut, utan ändra på den data som ligger på den ursprungliga platsen i minnet.

• Det kallas för "pedagogisk finess" när en lärare ljuger på det sättet.

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!"))

• 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 bara 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)

• 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)

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

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

Det blir inte alltid runtime-fel, men beteendet skiljer sig.

• 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.extend([4, 5])

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

• 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 = my_list + [4]

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

• 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 += [4]

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

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)

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)

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

Tupler

• En kommaseparerad sekvenser av objekt i Python-kod kallas för en tupel (eng. tuple).
• Omger vi en sådan tupel med hakparenteser, [ och ], så kommer Python skapa en lista av värdena i tupeln.
  • (Detta är också en typ av syntaktiskt socker, som vi dock har använt från dag 1.)

tuple1 = 1, 2, 3
print(tuple1)

• Notera att tupler skrivs ut med vanliga parenteser, ( och ).
• Vi använder oftast parenteser även när vi skriver tupelliteraler för tydlighet.

tuple1 = (1, 2, 3)
print(tuple1)

Tupler med 0 eller 1 element?

print(1 == (1, ))
print(type(()))
print(type((1)))
print(type((1, )))

Tupler är oföränderliga

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

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

Tupel-lista-konvertering

• Vi kan enkelt skapa en lista med alla element från en tupel och vice versa.
• Notera att varje gång vi gör en sådan "konvertering" så skapas en ny lista/tupel.

print(list(numbers_tuple))
my_list = (7, 9, 'e')
print(tuple(my_list))

Varför tupler när listor finns?

• Att listor kan förändras när de skickas till funktioner är en möjlig felkälla i många situationer.
• Använder vi en tupel är vi säkra på att den inte ändras.
• Python använder tupler internt till många saker (t.ex. hur argument överförs till funktioner, något vi kommer utnyttja längre fram i kursen).
• Tupler kan vara nycklar i en dict, det kan inte listor.

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 eller associationstabell (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 för dict

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

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)
    

Iterera över värden

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

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

• 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)
    

• 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, etc.
• 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 ett extra fiktivt exempel med ett användarnamn och ett fullständigt namn

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": 1917 } ]
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]=}")

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]=}")

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
    

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)
        

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, separator):
    # gå igenom listan med dictionaries
    for dictionary in list_of_dictionaries:
        print(separator)
        # gå igenom alla nyckel-värde-par i aktuellt dictionary
        for key, value in dictionary.items():
            print(f"The key '{key}' has the value: {value}")

print_dictionaries(pokemons, "pokemon:")

Bearbeta lista av dictionaries 1

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

print_dictionaries(books, "book:")

Bearbeta lista av dictionaries 2

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

Bearbeta lista av dictionaries 2

print_dictionaries(pokemons, 'pokemon:')
print_dictionaries(books, 'book:')

Leta efter värde i nästlad lista

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
    # når vi slutet av funktionen utan att ha hittat värdet vi letar efter så
    return False

nested_list = [ "a", ["b", "c"], "d", "e", ["f", "g"] ]
look_for_value("h", nested_list)

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

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

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?
  • 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...

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åller exempel på rekursion använder ofta suffixet "-ception" som en referens till filmen. Ordet "inception" har i sig ingenting med rekursion att göra.
• Codeception och Listception

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...

• 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 funktion $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.

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.

Summera en lista av heltal

• Vi vill summera listan [1, 2, 75, 6, 7]
• Med en for-loop:

def sum_list_for(values):
    pass

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

• Hur gör man samma sak rekursivt?

    result = 0
    for value in values:
        result += value
    return result

Ett första försök

def sum_list_rec(values):
    pass

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

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

• Vad har vi glömt?

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

• Vad bör anropet nedan bli?

sum_list_rec([])

• 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])=}")

• 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)=}")

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)=}")

• 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 beräkningar kan formuleras om till iterativa beräkningar, 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, implementation av programmeringsspråk, etc.
• Varför började vi ens prata om rekursion?
  • Rekursion lämpar sig särskilt bra för att hantera godtyckligt 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:])

Jorå, såatte... varför göra det på det här knöliga sättet när vi har loopar?

• Varför började vi prata om rekursion?
• Nästlade strukturer, när vi inte vet antalet nivåer av nästling.

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

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

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

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):
    print(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:])
    
    
look_for_value_rec_all('a', ['b', ['c', [['d'], 'a']]])


    

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, []))

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, []))

• 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, []))