Scala til backendudvikling og funktionel programmering · Lektion

Tænk rekursivt

Basistilfælde og rekursive trin.

Lektion 1 af 413 trin

Tænk rekursivt er en gratis Scala til backendudvikling og funktionel programmering-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Scala til backendudvikling og funktionel programmering, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Scala til backendudvikling og funktionel programmering-kurset indeholder 4 lektioner i alt.

Hvad rekursion betyder

Rekursion er, når en funktion kalder sig selv for at løse en mindre version af det samme problem.

I Scala passer rekursion naturligt til funktionel programmering, fordi det lader dig udtrykke løkker uden mutable variabler.

Enhver rekursiv funktion har brug for to ting: en måde at stoppe på og en måde at gøre problemet mindre på.

Basistilfældet først

Basistilfældet er det enkleste input, som funktionen kan besvare direkte uden yderligere rekursion.

Uden et basistilfælde ville funktionen kalde sig selv for evigt og gå ned med et stack overflow.

Design altid basistilfældet, før du skriver det rekursive trin.

def countdown(n: Int): Unit =
  if (n < 0) ()           // base case: stop
  else {
    println(n)
    countdown(n - 1)      // recursive step
  }

En første rekursiv funktion

Her er et komplet program, der lægger tallene fra 1 til n sammen.

Basistilfældet returnerer 0; det rekursive tilfælde lægger n til summen af alle tallene under det.

def sum(n: Int): Int =
  if (n == 0) 0
  else n + sum(n - 1)

@main def run(): Unit =
  println(sum(5))   // 15

Spor kaldende

Udvid kaldende i hånden for at forstå rekursion.

sum(3) bliver til 3 + sum(2), som bliver til 3 + 2 + sum(1), derefter 3 + 2 + 1 + sum(0).

Først når sum(0) returnerer 0, foldes kæden sammen til én værdi: 6.

// sum(3)
// = 3 + sum(2)
// = 3 + (2 + sum(1))
// = 3 + (2 + (1 + sum(0)))
// = 3 + (2 + (1 + 0))
// = 6

Rekursion på lister

Lister er rekursive af natur: En liste er enten tom (Nil) eller består af et hoved og en mindre hale.

Denne struktur passer direkte til rekursive funktioner. Den tomme liste er basistilfældet; hovedet plus rekursion på halen er det rekursive trin.

def length[A](xs: List[A]): Int = xs match {
  case Nil     => 0
  case _ :: t  => 1 + length(t)
}

Mønstermatch på halen

Mønsteret :: opdeler en ikke-tom liste i dens hoved og hale.

Hvert rekursivt kald arbejder på en strengt kortere liste, hvilket garanterer fremgang mod Nil.

Dette er den kanoniske måde at gennemløbe en liste rekursivt på i Scala.

def sumList(xs: List[Int]): Int = xs match {
  case Nil    => 0
  case h :: t => h + sumList(t)
}

@main def run(): Unit =
  println(sumList(List(1, 2, 3, 4)))  // 10

To rekursive kald

Nogle problemer forgrener sig i mere end ét rekursivt kald.

Det klassiske eksempel er Fibonacci, hvor hver værdi afhænger af de to foregående.

Denne naive version er enkel, men langsom, fordi den beregner de samme værdier igen og igen.

def fib(n: Int): Int =
  if (n < 2) n
  else fib(n - 1) + fib(n - 2)

@main def run(): Unit =
  println(fib(7))   // 13

Omkostningen ved stacken

Hvert rekursivt kald tilføjer en ramme til kaldstacken, som skal vente på, at det indre kald returnerer.

Ved meget dyb rekursion kan stacken blive opbrugt, så der kastes en StackOverflowError.

Hvis du tæller dybden og ikke kun størrelsen, bliver det lettere at forudsige denne risiko.

// This would overflow the stack for large n:
// def deep(n: Int): Int =
//   if (n == 0) 0 else 1 + deep(n - 1)
// deep(1000000)  // StackOverflowError

Mod basistilfældet

Den vigtige invariant ved rekursion er, at hvert kald skal bringe dig tættere på basistilfældet.

Hvis argumentet ikke bliver mindre eller aldrig når stopbetingelsen, slutter rekursionen aldrig.

Kontrollér dette, før du kører noget.

def reverse[A](xs: List[A]): List[A] = xs match {
  case Nil    => Nil
  case h :: t => reverse(t) :+ h   // t is smaller than xs
}

Rekursion kontra løkker

Imperativ kode bruger while-løkker med mutable tællere; funktionel kode bruger rekursion med immutable værdier.

Begge dele kan udtrykke de samme beregninger, men rekursion beskriver datastrukturen mere direkte.

I Scala vil du ofte foretrække rekursion eller funktioner af højere orden frem for rå løkker.

// Imperative
var total = 0
for (i <- 1 to 5) total += i

// Recursive
def sum(n: Int): Int = if (n == 0) 0 else n + sum(n - 1)

Design en rekursiv løsning

En pålidelig opskrift er: identificér basistilfældet, antag at det rekursive kald allerede fungerer på det mindre input, og kombiner derefter hovedet med resultatet.

Dette spring i tillid er kernen i rekursiv tænkning. Du stoler på det mindre kald og håndterer kun ét trin.

def maxOf(xs: List[Int]): Int = xs match {
  case h :: Nil => h
  case h :: t   => math.max(h, maxOf(t))
}

@main def run(): Unit =
  println(maxOf(List(3, 9, 2, 7)))  // 9

Hurtig kontrol

Test din forståelse af rekursiv struktur.

Besvar den i den interaktive lektion

Opsummering

Rekursion løser et problem ved at reducere det til en mindre udgave af sig selv.

Enhver rekursiv funktion har brug for et basistilfælde, der stopper, og et rekursivt trin, der gør inputtet mindre og fører det mod basistilfældet.

Lister med deres Nil- og hoved-hale-struktur er et ideelt sted at øve rekursiv tænkning. Hold øje med stackdybden ved meget store input.

Gratis at komme i gang

Lær Scala med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser: 39
Lektioner: 143

Start gratis Se hele kurset

Ofte stillede spørgsmål

Er lektionen “Tænk rekursivt” gratis?

Ja — hele teksten til “Tænk rekursivt” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Scala til backendudvikling og funktionel programmering-kurset, skal du opgradere til CoddyKit PRO. Scala til backendudvikling og funktionel programmering-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Tænk rekursivt”?

Basistilfælde og rekursive trin. Du øver dig i Scala til backendudvikling og funktionel programmering med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på Scala til backendudvikling og funktionel programmering?

Der kræves ingen tidligere erfaring. Scala til backendudvikling og funktionel programmering på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 1 af 4.

Hvor lang tid tager lektionen “Tænk rekursivt”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne Scala til backendudvikling og funktionel programmering-lektion?

Ja. Alle Scala til backendudvikling og funktionel programmering-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

← Tilbage til Scala til backendudvikling og funktionel programmering