Förstå rekursion

Datastrukturer och algoritmer i Python

Miriam Antona

Software engineer

Definition

• En funktion som anropar sig själv
• Kan användas i nästan alla situationer där vi använder loopar
  • ersätt loopar med rekursion
• Kan lösa problem som verkar komplexa vid första anblicken

Exempel – fakultet

$n!$

Exempel – fakultet

$n!=n$ · $(n-1)$ · $(n-2)$ · $...$ · $1$

$5!=$ $5$ · $4$ · $3$ · $2$ · $1=120$

def factorial(n):
  result = 1
  while n > 1:
    result = n * result
    n -= 1
  return result

factorial(5)

120

Exempel – fakultet med rekursion

$n!= n$ · $(n-1)!$

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

• Körs för evigt!

Exempel – identifiera basfallet

• Lägg till ett villkor
  • förhindrar att algoritmen körs för evigt
• Basfall för fakultet -> $n=1$

def factorial_recursion(n):
  if n == 1:

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

120

Hur rekursion fungerar

• Datorn använder en stack för att hålla reda på funktionerna
  • Anropsstack

Hur rekursion fungerar

• factorial(5) startar
• Innan factorial(5) är klar -> factorial(4) startar
• Innan factorial(4) är klar -> factorial(3) startar

Hur rekursion fungerar

• factorial(5) startar
• Innan factorial(5) är klar -> factorial(4) startar
• Innan factorial(4) är klar -> factorial(3) startar
• Innan factorial(3) är klar -> factorial(2) startar

Hur rekursion fungerar

• factorial(5) startar
• Innan factorial(5) är klar -> factorial(4) startar
• Innan factorial(4) är klar -> factorial(3) startar
• Innan factorial(3) är klar -> factorial(2) startar
• Innan factorial(2) är klar -> factorial(1) startar

Hur rekursion fungerar

• factorial(5) startar
• Innan factorial(5) är klar -> factorial(4) startar
• Innan factorial(4) är klar -> factorial(3) startar
• Innan factorial(3) är klar -> factorial(2) startar
• Innan factorial(2) är klar -> factorial(1) startar

Hur rekursion fungerar

• factorial(1) är klar
  • returnerar 1
• factorial(2) är klar

Hur rekursion fungerar

• factorial(1) är klar
  • returnerar 1
• factorial(2) är klar
  • returnerar 2

Hur rekursion fungerar

• factorial(1) är klar
  • returnerar 1
• factorial(2) är klar
  • returnerar 2
• factorial(3) är klar
  • returnerar 6

Hur rekursion fungerar

• factorial(1) är klar
  • returnerar 1
• factorial(2) är klar
  • returnerar 2
• factorial(3) är klar
  • returnerar 6
• factorial(4) är klar
  • returnerar 24

Hur rekursion fungerar

• factorial(1) är klar
  • returnerar 1
• factorial(2) är klar
  • returnerar 2
• factorial(3) är klar
  • returnerar 6
• factorial(4) är klar
  • returnerar 24
• factorial(5) är klar
  • returnerar 120

Hur rekursion fungerar

• factorial(1) är klar
  • returnerar 1
• factorial(2) är klar
  • returnerar 2
• factorial(3) är klar
  • returnerar 6
• factorial(4) är klar
  • returnerar 24
• factorial(5) är klar
  • returnerar 120

Dynamisk programmering

• Optimeringsteknik
• Används främst vid rekursion
• Kan minska komplexiteten hos rekursiva algoritmer
• Används för:
  • Problem som kan delas upp i mindre delproblem
  • Delproblem som överlappar
• Lösningar på delproblem sparas, vilket undviker omberäkning
  • Memoization

Nu kör vi en övning!

Datastrukturer och algoritmer i Python