TDDE44 Programmering, grundkurs

Föreläsning 2.1-2.2

Johan Falkenjack, johan.falkenjack@liu.se

• Ofiltrerad.

Föreläsningsöversikt FÖ 2.1-2.2

• Programflöde - Anropsstacken och scope
• Upprepning
  • Rekursion
  • Iteration
    • Fördefinierat antal upprepningar - for
    • Generell iteration - while

Anropsstacken (eng. call stack)

Datastrukturen stack

A stack of plates

• En stapel av objekt:
  • Lägg till objekt på toppen (eng: push)
  • Ta bort översta objektet (eng: pop)
  • Alla andra objekt i stacken är otillgängliga
• Liknelse: Lista där nya element bara kan läggas till i slutet (append), och bara det sista elementet kan tas bort (pop).

Källa: Wikipedia

Anropsstacken

• Stack som håller reda på var vi befinner oss i exekveringen av ett Python-skript.
  • Innehåller omgivningar (eng: frames) med de variabler och funktioner som finns tillgängliga.
• En speciell Global frame skapas när ett Python-skript startar och är det första elementet som läggs på anropsstacken.
• Variabler och funktioner som skapas lagras i denna omgivning.

• Inte något vi behöver hantera manuellt, men vi måste vara medvetna om den och vad den innebär.
• Mycket snack för något som verkar ganska irrelevant.
• Intressant först när funktion anropas

Programflöde - funktionsanrop

• Ett pythonprogram tolkas sekventiellt av pythontolken.
• Vi tänker oss att vi har en körmarkör som pekar på vad det som ska utföras näst
• När pythontolken ser ett funktionanrop görs följande
  1. eventuella argument i funktionsanropet evalueras
  2. en frame för funktionsanropet skapas på toppen av anropsstacken och eventuella argument binds till funktionens parametrar
  3. den anropade funktionens funktionskropp utförs sekventiellt - körmarkören flyttas till funktionskroppen
  4. när funktionen är klar tas dess frame bort från toppen anropsstacken och
  5. körmarkören flyttas tillbaka dit anropet påträffades och funktionsanropet substitueras (ersätts) av funktionens returvärde

Exempel

print("Första raden")

def calc_double(value):
    new_value = value * 2
    print("värdet på value:", value)
    print("värdet på new_value:", new_value)
    return new_value

def main():
    print("Nu körs main()")
    value = 5
    double = calc_double(value)
    print("Dubbla värdet är", double)

main()
print("Nu är programmet slut!")

(Python Tutor eller Spegel på CEMC på University of Waterloo)

• Beroende på tid, kör exemplet i Pythontutor eller lämna det som övning.

Scope

• Den kontext där en variabel är giltig.
• En variabel som skapats inne i en funktion kallar vi för lokal variabel
• Scopet för en lokal variabel är den frame som skapades vid funktionsanropet.
  • Dvs. den lokala variabeln är endast giltig och tillgänglig i funktionsanropets frame.
• Variabler med samma namn kan existera i olika scopes med olika värden.

• Håll tungan rätt i mun.

Lokala variabler

• Funktionens parametrar blir lokala variabler i funktionen, med argumenten som initialt värde.

def calc_double(value):
    new_value = value * 2
    print("värdet på value:", value)
    print("värdet på new_value:", new_value)
    return new_value

value = 10
print("värdet på value:", value)
calc_double(value)

print("värdet på value:", value)

print("värdet på new_value:", new_value)

Upprepning och programmatisk bearbetning av sekvenser

De flesta beräkningarna och processer i datorer är sekventiella

• Information läses sekventiellt från start till slut.
• Vad får detta för konsekvenser?

Hur lång är längsta figuren?

Hur lång är längsta figuren?

Hur lång är längsta figuren?

120	100	160
A	B	C

A = 120
B = 100
C = 160

if A > B:
    tallest = A
else:
    tallest = B
if C > tallest:
    tallest = C
    
print("The tallest height is " + str(tallest))

The tallest height is 160

Hur lång är längsta figuren?

Hur lång är längsta figuren?

Från datorns perspektiv

• Har datorn en översiktsbild? Kan datorn titta på en hel sekvens på en gång?
  

• Datorn kan "titta" på ett element i taget, möjligtvis två precis vid en jämförelse
• Vi måste tillhandahålla arbetsminne
• Datorn kommer inte ihåg något "automatiskt"

Vad behövs för att bearbeta en sekvens av data?

• något sätt att gå igenom sekvensen
• något sätt att beskriva regler för vad som göras beroende på vad för värden vi har i sekvensen

Rekursion

Upprepning med byggstenarna vi redan har.

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

Konceptet rekursion

• Självlikhet eller självreferens.
• Fenomen som i sin struktur innehåller en 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 i naturligt språk 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

• Logaritmisk spiral enligt gyllene snittet.

Vad har detta med programmering att göra?

• Redan tidigare: Kodblock som innehåller kodblock.
  • T.ex. funktioner som innehåller villkorssatser som i sin tur innehåller villkorssatser.

• Nu: Rekursiva processer.
  • Funktioner som direkt anropar sig själva.

• Sen: 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.

En viktig intuition lånad från matematiken

• Vi kan uttrycka summan av alla heltal på det slutna intervallet $[1, n]$ på följande vis:

$$\sum_{i=1}^{n}{i} = 1 + 2 + \ldots + (n-1) + n$$

• Vi kan bryta ut $1$ eller $n$ från summan och ändå få samma resultat

$$\begin{align} 1+\sum_{i=2}^{n}{i} &= 1 + (2 + \ldots + (n-1) + n)\\ n+\sum_{i=1}^{n-1}{i} &= n + (1 + 2 + \ldots + (n-1)) = (1 + 2 + \ldots + (n-1)) + n \end{align}$$

• Alltså gäller att

$$\sum_{i=1}^{n}{i} = 1+\sum_{i=2}^{n}{i} = n+\sum_{i=1}^{n-1}{i}$$

Forts.

• Om vi beskriver summan i form av en funktion $f(n)$:

$$f(n) = \sum_{i=1}^{n}{i}$$

• Så gäller alltså att:

$$f(n) = n+f(n-1)$$

• Den känner att det rycker lite i induktionsnerven just nu är på helt rätt spår. Rent matematiskt är induktion och rekursion olika sidor av samma mynt.

Klassiskt exempel: Beräkna fakulteten av ett tal

• Definition för alla positiva heltal $n$ gäller att:

$$ n! = \prod^n_{i=1}i $$

• T.ex. $5! = 1 \times 2 \times 3 \times 4 \times 5 = 120$
  • (se mer på Wikipedia)

• Med samma resonemang som för summan kan vi definiera:

$$ n! = n\times(n-1)! $$

• Dvs. $5! = 5\times(5-1)! = 5\times4!$ osv.

Fakulteten i kod

$$ n! = n\times(n-1)! $$

def factorial(n):
    return n * factorial(n-1)

print(factorial(5))

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
Cell In[3], line 4
      1 def factorial(n):
      2     return n * factorial(n-1)
----> 4 print(factorial(5))

Cell In[3], line 2, in factorial(n)
      1 def factorial(n):
----> 2     return n * factorial(n-1)

Cell In[3], line 2, in factorial(n)
      1 def factorial(n):
----> 2     return n * factorial(n-1)

    [... skipping similar frames: factorial at line 2 (2969 times)]

Cell In[3], line 2, in factorial(n)
      1 def factorial(n):
----> 2     return n * factorial(n-1)

RecursionError: maximum recursion depth exceeded

def factorial(n):
    return n * factorial(n-1)

print(factorial(5))

Hålla tungan i rätt mun

• Parametern n i vår Python-kod är bara ett heltal, vilket som helst.
• Vår definition av $n!$ gällde bara för positiva heltal.

Basfall

• Ett trivialt fall för vilket resultatet är givet, och inget rekursivt anrop behöver göras.
• För fakulteten: $1! = 1$

def factorial(n):
    # tekniskt sett brukar man också definiera 0! = 1, så
    if n <= 1:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5))

120

def factorial(n)
    # tekniskt sett brukar man också definiera 0! = 1, så:
    if n <= 1:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5))
print(factorial(10))

Ungefärlig struktur hos enkelrekursiv funktion

def rec_fun(parameter):
    if <parameter utgör basfallet>:
        return <trivialt resultat>
    if <parameter uppfyller omständighet>:
        return kombinera(hantera_omständighet(parameter), rec_fun(förenkla(parameter)))
    else:
        return kombinera(gör_något_annat(parameter), rec_fun(förenkla(parameter)))
        # eller ibland
        return rec_fun(förenkla(parameter)) # när vi bara ska gå direkt vidare till nästa steg

• Ofta utgörs kombineringssteget snarare av en binär operator än ett funktionsanrop med två argument så som kombinera i mallen ovan.

• Inte en speciell syntax, bara ett generellt mönster.
• Vad gör denna enkel? Vi gör som mest ett rekursivt anrop varje gång funktionen exekveras.
• Stoppvillkor och trivialt basfall.
• Var är do_something?
• Kombinationsoperation.
• Rekursionssteg.

Generell approach

• 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.
• Precis som vi förenklade summan i

$$\sum_{i=1}^{n}{i} = n+\sum_{i=1}^{n-1}{i} \qquad\text{eller}\qquad \sum_{i=1}^{n}{i} = 1+\sum_{i=2}^{n}{i} = $$

• Hur försäkrar vi att någon del har en trivial lösning?
• Hur skall uppdelningen i delproblem ske så att vi närmar oss det trivialt enkla basfallet?
• Hur skall delproblemens resultat kombineras med varandra?

Steg för steg

1. Identifiera det enklaste möjliga giltiga anropet till funktionen.
2. Identifiera minsta möjliga delproblem vi kan lösa för fall som inte är basfallet.
3. Identifiera alla olika sätt på vilket det minsta delproblemet kan behöva hanteras.
4. Hitta ett sätt att förenkla problemet, dvs. ett sätt att närma oss det triviala basfallet.
5. Avgör hur lösningen på ett aktuellt delproblem ska kombineras med lösningen av resten av problemet.

Generellt tankeknep

• Antag att vi redan har en funktion som löser problemet givet att vi kan definiera lösningen för basfallet och de möjliga första delproblemen.
• Skriv bara kod för att hantera dessa och förenkla bort första delproblemet.
• Anropa funktionen som löser problemet för resten av problemet.
• Funktionen som kan lösa resten av problemet är samma funktion som vi just implementerat.

Exempelproblem

• Skriv en funktion sum_ints som summerar alla heltal i en lista. Listan kan innehålla heltal och strängar.

def sum_ints(values):
    ...
    
print(sum_ints(...))

• sum_ints([]) == 0
• sum_ints([4]) == 4 + sum_ints([]) == 4 + 0
• sum_ints(['a']) == sum_ints([]) == 0
• Behöver vi fler? Vad gör vi med resten? sum_rest?

Basfall: Om values är tomma listan

def sum_ints(values):
    if values == []:
        return 0
    
print(sum_ints([]))

0

Om values börjar med ett heltal

def sum_ints(values):
    if values == []:
        return 0
    if type(values[0]) == int:
        return values[0] + sum_ints(values[1:])
    
print(sum_ints([1]))

1

Om values inte börjar med ett heltal

def sum_ints(values):
    if values == []:
        return 0
    if type(values[0]) == int:
        return values[0] + sum_ints(values[1:])
    else:
        return sum_ints(values[1:])
    
print(sum_ints(['a']))

0

Tester

print("sum_ints([])", '->', sum_ints([]))
print("sum_ints([1])", '->', sum_ints([1]))
print("sum_ints(['a'])", '->', sum_ints(['a']))
print("sum_ints([1, 4, 2])", '->', sum_ints([1, 4, 2]))
print("sum_ints(['a', 'b', 'c'])", '->', sum_ints(['a', 'b', 'c']))
print("sum_ints(['a', 1, 'b', 4, 2, 'c'])", '->', sum_ints(['a', 1, 'b', 4, 2, 'c']))

sum_ints([]) -> 0
sum_ints([1]) -> 1
sum_ints(['a']) -> 0
sum_ints([1, 4, 2]) -> 7
sum_ints(['a', 'b', 'c']) -> 0
sum_ints(['a', 1, 'b', 4, 2, 'c']) -> 7

Hur lång är längsta figuren?

def tallest(heights):
    ...

measurements = [
     1,  2, 71,  6, 56,  5, 57, 55, 84,
    17, 89, 13, 31, 22, 30, 34, 65, 61, 
    69,  3,  2, 62, 68, 86,  8, 23, 67,
    14,  7,  2, 32,  7, 11, 63, 60, 16,
    32,  2, 70, 89,  3, 72, 68, 59, 15,
    53,  7, 24,  8, 26, 28, 67, 54, 64,
]
print(tallest(measurements))

None

def tallest(heights):
    if heights == []:
        return 0
    tallest_in_rest = tallest(heights[1:])
    if heights[0] > tallest_in_rest:
        return heights[0]
    else:
        return tallest_in_rest
    
print(tallest(measurements))

89

Basfall: Om heights är tomma listan

def tallest(heights):
    if heights == []:
        return 0
    
print(tallest(measurements))

None

Rekurssionssteg: Hitta den längsta längden i resten av listan

def tallest(heights):
    if heights == []:
        return 0
    tallest_in_rest = tallest(heights[1:])
    
print(tallest(measurements))

None

Returnera den längsta längden

def tallest(heights):
    if heights == []:
        return 0
    tallest_in_rest = tallest(heights[1:])
    if heights[0] > tallest_in_rest:
        return heights[0]
    else:
        return tallest_in_rest
    
print(tallest(measurements))

89

# Tester

print("tallest([10, 79, 41])", "->", tallest([10, 79, 41]))
print("tallest([40, 27, 12, 47, 100, 66, 59])", "->", tallest([40, 27, 12, 47, 100, 66, 59]))
print("tallest([32, 61, 55, 95, 49, 75])", "->", tallest([32, 61, 55, 95, 49, 75]))

tallest([10, 79, 41]) -> 79
tallest([40, 27, 12, 47, 100, 66, 59]) -> 100
tallest([32, 61, 55, 95, 49, 75]) -> 95

Hur lång är längsta figuren?

• Ett alternativt sätt att formulera lösningen: Iterativ processlösning
• Vi använder parametern tallest_found som ackumulator som lagrar resultatet så långt som det har beräknats.

def tallest_iter(heights, tallest_found):
    ...
    
print(tallest_iter(measurements, 0))

def tallest_iter(heights, tallest_found):
    if heights == []:
        return tallest_found
    if heights[0] > tallest_found:
        return tallest_iter(heights[1:], heights[0])
    else:
        return tallest_iter(heights[1:], tallest_found)
    
print(tallest_iter(measurements, 0))

89

Basfall: Om heights är tomma listan

def tallest_iter(heights, tallest_found):
    if heights == []:
        return tallest_found
    
print(tallest_iter(measurements, 0))

None

Om första elementet är längre än längsta längden vi sett

• Så letar vi vidare med det elementet som den längsta längd vi sett.

def tallest_iter(heights, tallest_found):
    if heights == []:
        return tallest_found
    if heights[0] > tallest_found:
        return tallest_iter(heights[1:], heights[0])
    
print(tallest_iter(measurements, 0))

None

Om inte

• Så letar vi vidare med samma längsta längd som tidigare.

def tallest_iter(heights, tallest_found):
    if heights == []:
        return tallest_found
    if heights[0] > tallest_found:
        return tallest_iter(heights[1:], heights[0])
    else:
        return tallest_iter(heights[1:], tallest_found)
    
print(tallest_iter(measurements, 0))

89

# Tester

print("tallest_iter([86, 23, 75], 0)", "->", tallest_iter([86, 23, 75], 0))
print("tallest_iter([21, 12, 71, 79], 0)", "->", tallest_iter([21, 12, 71, 79], 0))
print("tallest_iter([86, 22, 65, 88, 97, 80, 83], 0)", "->", tallest_iter([86, 22, 65, 88, 97, 80, 83], 0))

tallest_iter([86, 23, 75], 0) -> 86
tallest_iter([21, 12, 71, 79], 0) -> 79
tallest_iter([86, 22, 65, 88, 97, 80, 83], 0) -> 97

Enkelrekursiv funktion som uttrycker iterativ processlösning

def rec_fun_iter(parameter, ackumulator):
    if <parameter utgör basfallet>:
        return ackumulator
    if <parameter uppfyller omständighet>:
        return rec_fun_iter(förenkla(parameter), kombinera(hantera_omständighet(parameter), ackumulator))
    else:
        return rec_fun_iter(förenkla(parameter), kombinera(gör_något_annat(parameter), ackumulator))
        # eller ibland
        return rec_fun_iter(förenkla(parameter), ackumulator) # när vi bara ska gå direkt vidare till nästa steg

Rekursiv kontra iterativ processlösning

• Rekursiv process: Kombinationen av lösningarna till alla delproblem utförs först när vi nått basfallet.
• Iterativ process: Lösningarna på delproblemen kombineras i en ackumulator allt eftersom de beräknas.
• Olika problem kan lämpa sig bättre för ena eller andra approachen, i många fall går båda lika bra och i vissa komplexa fall blandar vi båda teknikerna.
• Efter föreläsningen: Prova att köra både tallest och tallest_iter i Python Tutor.

Sätt att slippa skicka med en ackumulator vid första anropet

• I tallest_iter skickade vi med 0 till första anropet som ackumulatorns första värde.
  • Verkar onödigt.
  • Kan orsaka fel om vi skulle råka skicka fel startvärde för ackumulatorn.
• Wrapperfunktion: Skapa en funktion tallest(heights) som bara anropar tallest_iter(heights, 0).
• Nästlade funktioner: Skapa en funktion tallest(heights), lägg definitionen av tallest_iter inne i den funktionen, och anropa tallest_iter(heights, 0).
• Defaultparameter: Definiera tallest_iter med ett standardvärde på tallest_found som används om vi inte skickar med ett ackumulatorvärde.

def tallest_iter(heights, tallest_found=0):
    ...

Exempeluppgifter från tidigare tentor

is_increasing_rec

En talföljd $a_1, a_2, a_3, \dots$ kallas växande om $a_{n+1}-a_{n} \geq 0$ för alla $n$. Dvs. om en talföljd är växande gäller att $a_{1}\leq a_{2}\leq\dots\leq a_{n}$ för alla $a_{n}$ i talföljden.

Skriv funktionen is_increasing_rec(sequence) vars argument är en lista av heltal. Funktionen ska returnera True om sequence är växande, annars ska den returnera False. Anta att sequence har minst 2 element.

# Skriv funktionen `is_increasing_rec(sequence)` vars argument är en lista av heltal. Funktionen ska returnera `True` om `sequence` är växande, annars ska den returnera `False`. Du kan anta att sequence har minst 2 element.

def is_increasing_rec(sequence):
    ...

"""
>>> is_increasing_rec([1, 2, 3])
True
>>> is_increasing_rec([3, 2, 1])
False
>>> is_increasing_rec([1, 3, 2])
False
>>> is_increasing_rec([1, 2, 2, 3])
True
>>> is_increasing_rec([10, 100, 1000])
"""

def is_increasing_rec(sequence):
    if len(sequence) < 2:
        return True
    if sequence[0] > sequence[1]:
        return False
    return is_increasing_rec(sequence[1:])

def is_increasing_rec2(sequence):
    # Om första elementet är större än andra så är sequence inte växande och
    # vi bryter rekursionen genom att returnera False:
    if sequence[0] > sequence[1]:
        return False
    # Om sequence är längre än 2 måste vi kontrollera resten av sequence:
    if len(sequence) > 2:
        return is_increasing_rec2(sequence[1:])
    # Annars vet vi att vi inte hittat några element i fel ordning och kan
    # returnera True
    else:
        return True

def is_increasing_rec3(sequence):
    # Om sequence är exakt två element vet vi att bara dessa spelar roll och
    # kontrollerar att förhållandet gäller för dem:
    if len(sequence) == 2:
        return sequence[0] <= sequence[1]
    # Annars måste vi kontrollera att förhållandet gäller för både de första
    # två elementen och för resten av elementen.
    else:
        return sequence[0] <= sequence[1] and is_increasing_rec3(sequence[1:])

Basfall: Om sequence är kortare än 2 element

• Trivialt sant eftersom inga element kan vara i fel ordning om vi har färre än 2 element, så vi returnerar True.

# Skriv funktionen `is_increasing_rec(sequence)` vars argument är en lista av heltal. Funktionen ska returnera `True` om `sequence` är växande, annars ska den returnera `False`. Du kan anta att sequence har minst 2 element.

def is_increasing_rec(sequence):
    if len(sequence) < 2:
        return True

None

Också en typ av basfall: Om första värdet är större än andra värdet

• Talföljden är uppenbart inte växande, så vi returnerar False

# Skriv funktionen `is_increasing_rec(sequence)` vars argument är en lista av heltal. Funktionen ska returnera `True` om `sequence` är växande, annars ska den returnera `False`. Du kan anta att sequence har minst 2 element.

def is_increasing_rec(sequence):
    if len(sequence) < 2:
        return True
    if sequence[0] > sequence[1]:
        return False

None

Rekursionssteg: Kontrollera att resten av talföljden är stigande

# Skriv funktionen `is_increasing_rec(sequence)` vars argument är en lista av heltal. Funktionen ska returnera `True` om `sequence` är växande, annars ska den returnera `False`. Du kan anta att sequence har minst 2 element.

def is_increasing_rec(sequence):
    if len(sequence) < 2:
        return True
    if sequence[0] > sequence[1]:
        return False
    return is_increasing_rec(sequence[1:])

# Tester:

print("is_increasing_rec([1, 2, 3])", "->", is_increasing_rec([1, 2, 3]))
print("is_increasing_rec([3, 2, 1])", "->", is_increasing_rec([3, 2, 1]))
print("is_increasing_rec([1, 3, 2])", "->", is_increasing_rec([1, 3, 2]))
print("is_increasing_rec([1, 2, 2, 3])", "->", is_increasing_rec([1, 2, 2, 3]))
print("is_increasing_rec([10, 100, 1000])", "->", is_increasing_rec([10, 100, 1000]))

is_increasing_rec([1, 2, 3]) -> True
is_increasing_rec([3, 2, 1]) -> False
is_increasing_rec([1, 3, 2]) -> False
is_increasing_rec([1, 2, 2, 3]) -> True
is_increasing_rec([10, 100, 1000]) -> True

Förkortad lösning

• Vi kan utnyttja logiska operatorn and för att skippa en if-sats.

# Skriv funktionen `is_increasing_rec(sequence)` vars argument är en lista av heltal. Funktionen ska returnera `True` om `sequence` är växande, annars ska den returnera `False`. Du kan anta att sequence har minst 2 element.

def is_increasing_rec(sequence):
    if len(sequence) < 2:
        return True
    return sequence[0] <= sequence[1] and is_increasing_rec(sequence[1:]) # Blir False om sequence[0] > sequence[1]

# Tester:

print("is_increasing_rec([1, 2, 3])", "->", is_increasing_rec([1, 2, 3]))
print("is_increasing_rec([3, 2, 1])", "->", is_increasing_rec([3, 2, 1]))
print("is_increasing_rec([1, 3, 2])", "->", is_increasing_rec([1, 3, 2]))
print("is_increasing_rec([1, 2, 2, 3])", "->", is_increasing_rec([1, 2, 2, 3]))
print("is_increasing_rec([10, 100, 1000])", "->", is_increasing_rec([10, 100, 1000]))

is_increasing_rec([1, 2, 3]) -> True
is_increasing_rec([3, 2, 1]) -> False
is_increasing_rec([1, 3, 2]) -> False
is_increasing_rec([1, 2, 2, 3]) -> True
is_increasing_rec([10, 100, 1000]) -> True

sum_of_digits_rec

Skriv funktionen sum_of_digits_rec(int_value) vars argument int_value är ett heltal större än 0. Funktionen ska returnera summan av alla siffror i talet.

>>> sum_of_digits_rec(9)
9
>>> sum_of_digits_rec(42)
6
>>> sum_of_digits_rec(999)
27
>>> sum_of_digits_rec(1234)
10

# Skriv funktionen `sum_of_digits_rec(int_value)` vars argument `int_value` är ett heltal större än `0`. Funktionen ska returnera summan av alla siffror i talet.

def sum_of_digits_rec(int_value):
    ...

def sum_of_digits_rec(int_value):
    if int_value == 0:
        return 0
    return int_value % 10 + sum_of_digits_rec(int_value // 10)

def sum_of_digits_rec2(int_value):
    def inner(str_value):
        if not str_value:
            return 0
        return int(str_value[0]) + sum_of_digits_rec2(str_value[1:])
    return inner(str(int_value))

Basfall: Om int_value är 0

• Siffersumman är trivialt lika med 0.

# Skriv funktionen `sum_of_digits_rec(int_value)` vars argument `int_value` är ett heltal större än `0`. Funktionen ska returnera summan av alla siffror i talet.

def sum_of_digits_rec(int_value):
    if int_value == 0:
        return 0

None

Rekursionssteg

• Ta ut värdet i sista position med % 10, addera till siffersumman av talet med sista värdet borttaget mha. heltalsdivision // 10.
  • (Nedrundningsdivision, men för positiva heltal är det ekvivalent.)

# Skriv funktionen `sum_of_digits_rec(int_value)` vars argument `int_value` är ett heltal större än `0`. Funktionen ska returnera summan av alla siffror i talet.

def sum_of_digits_rec(int_value):
    if int_value == 0:
        return 0
    return int_value % 10 + sum_of_digits_rec(int_value // 10)

# Tester:

print("sum_of_digits_rec(9)", "->", sum_of_digits_rec(9))
print("sum_of_digits_rec(42)", "->", sum_of_digits_rec(42))
print("sum_of_digits_rec(999)", "->", sum_of_digits_rec(999))
print("sum_of_digits_rec(1234)", "->", sum_of_digits_rec(1234))

sum_of_digits_rec(9) -> 9
sum_of_digits_rec(42) -> 6
sum_of_digits_rec(999) -> 27
sum_of_digits_rec(1234) -> 10

Om kongruens och heltalsaritmetiken inte känns bekväm än

• Använd typkonvertering och använd strängoperationer:

# Skriv funktionen `sum_of_digits_rec(int_value)` vars argument `int_value` är ett heltal större än `0`. Funktionen ska returnera summan av alla siffror i talet.

def sum_of_digits_rec(int_value):
    str_value = str(int_value)
    if len(str_value) == 1:
        return int_value
    return int(str_value[0]) + sum_of_digits_rec(int(str_value[1:]))

print("sum_of_digits_rec(9)", "->", sum_of_digits_rec(9))
print("sum_of_digits_rec(42)", "->", sum_of_digits_rec(42))
print("sum_of_digits_rec(999)", "->", sum_of_digits_rec(999))
print("sum_of_digits_rec(1234)", "->", sum_of_digits_rec(1234))

sum_of_digits_rec(9) -> 9
sum_of_digits_rec(42) -> 6
sum_of_digits_rec(999) -> 27
sum_of_digits_rec(1234) -> 10

censor_words_rec

Skriv funktionen censor_words_rec(words, bad_words) som returnerar en lista där förekomster av ord i listan bad_words som finns med i listan words ersatts med strängen 'XXXX'. Både words och bad_words är listor som innehåller noll eller fler strängar.

>>> censor_words_rec(['hund', 'en', 'blå', 'bil', 'katt'], ['katt', 'hund'])
['XXXX', 'en', 'blå', 'bil', 'XXXX']
>>> censor_words_rec(['hund', 'en', 'blå', 'bil', 'katt'], [])
['hund', 'en', 'blå', 'bil', 'katt']
>>> censor_words_rec([], ['katt', 'hund'])
[]

# Skriv funktionen `censor_words_rec(words, bad_words)` som returnerar en lista där förekomster av ord i listan `bad_words` som finns med i listan `words` ersatts med strängen `'XXXX'`. Både `words` och `bad_words` är listor som innehåller noll eller fler strängar.

def censor_words_rec(words, bad_words):
    ...

def censor_words_rec(words, bad_words):
    if not words:
        return []
    if words[0] in bad_words:
        return ['XXXX'] + censor_words_rec(words[1:], bad_words)
    else:
        return [words[0]] + censor_words_rec(words[1:], bad_words)
        # alt.
        # return words[0:1] + censor_words_rec(words[1:], bad_words)
        
# Eftersom `bad_words` inte ändras under rekursionen kan vi också skriva om funktionen så att den använder en inre funktion som bara tar en parameter, `words`. Det kan bli lite prydligare.

def censor_words_rec_wi(words, bad_words):
    def inner(words):
        if not words:
            return []
        if words[0] in bad_words:
            return ["XXXX"] + inner(words[1:])
        else:
            return [words[0]] + inner(words[1:])
    return inner(words)

Basfall: Om words är tomma listan

• Trivialt resultat, inga ord finns, inga ord ska censureras, returnera [].

# Skriv funktionen `censor_words_rec(words, bad_words)` som returnerar en lista där förekomster av ord i listan `bad_words` som finns med i listan `words` ersatts med strängen `'XXXX'`. Både `words` och `bad_words` är listor som innehåller noll eller fler strängar.

def censor_words_rec(words, bad_words):
    if words == []:
        return []

Om första ordet ska censureras

# Skriv funktionen `censor_words_rec(words, bad_words)` som returnerar en lista där förekomster av ord i listan `bad_words` som finns med i listan `words` ersatts med strängen `'XXXX'`. Både `words` och `bad_words` är listor som innehåller noll eller fler strängar.

def censor_words_rec(words, bad_words):
    if words == []:
        return []
    if words[0] in bad_words:
        return ['XXXX'] + censor_words_rec(words[1:], bad_words)

Annars:

# Skriv funktionen `censor_words_rec(words, bad_words)` som returnerar en lista där förekomster av ord i listan `bad_words` som finns med i listan `words` ersatts med strängen `'XXXX'`. Både `words` och `bad_words` är listor som innehåller noll eller fler strängar.

def censor_words_rec(words, bad_words):
    if words == []:
        return []
    if words[0] in bad_words:
        return ['XXXX'] + censor_words_rec(words[1:], bad_words)
    else:
        return [words[0]] + censor_words_rec(words[1:], bad_words)

# Tester:

print("censor_words_rec(['hund', 'en', 'blå', 'bil', 'katt'], ['katt', 'hund'])", "->", censor_words_rec(['hund', 'en', 'blå', 'bil', 'katt'], ['katt', 'hund']))
print("censor_words_rec(['hund', 'en', 'blå', 'bil', 'katt'], [])", "->", censor_words_rec(['hund', 'en', 'blå', 'bil', 'katt'], []))
print("censor_words_rec([], ['katt', 'hund'])", "->", censor_words_rec([], ['katt', 'hund']))

censor_words_rec(['hund', 'en', 'blå', 'bil', 'katt'], ['katt', 'hund']) -> ['XXXX', 'en', 'blå', 'bil', 'XXXX']
censor_words_rec(['hund', 'en', 'blå', 'bil', 'katt'], []) -> ['hund', 'en', 'blå', 'bil', 'katt']
censor_words_rec([], ['katt', 'hund']) -> []