Grundlæggende rekursion
Rekursive funktioner
Grundlæggende rekursion 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 er rekursion?
Rekursion er, når en funktion kalder sig selv for at løse en mindre version af det samme problem. Det passer naturligt til funktionel programmering, hvor mange løkker erstattes af selvrefererende definitioner.
To vigtige dele
Alle korrekte rekursive funktioner har brug for:
- et basistilfælde, der stopper rekursionen.
- et rekursivt tilfælde, der bevæger sig hen imod basistilfældet.
Uden et basistilfælde, der kan nås, fortsætter rekursionen for evigt.
Fakultet
Det klassiske eksempel: n! = n * (n-1)!, hvor 0! = 1 er basistilfældet.
object Main {
def factorial(n: Int): Int =
if (n <= 1) 1
else n * factorial(n - 1)
def main(args: Array[String]): Unit = {
println(factorial(5))
}
}Sporing af kald
Hvert rekursivt kald sættes på pause og venter på det indre resultat. factorial(3) udfoldes til 3 * (2 * (1)). Multiplikationerne udføres, når kaldende returnerer.
object Main {
def factorial(n: Int): Int = {
println(s"entering factorial($n)")
if (n <= 1) 1 else n * factorial(n - 1)
}
def main(args: Array[String]): Unit = {
println("result = " + factorial(3))
}
}Sum af en liste
Rekursion over en liste: summen er hovedet plus summen af halen, hvor den tomme liste har summen nul.
object Main {
def sum(xs: List[Int]): Int = xs match {
case Nil => 0
case h :: t => h + sum(t)
}
def main(args: Array[String]): Unit = {
println(sum(List(1, 2, 3, 4)))
}
}Længden af en liste
Det samme mønster beregner længden: en tom liste har længden 0, ellers er længden 1 plus længden af halen.
object Main {
def length[A](xs: List[A]): Int = xs match {
case Nil => 0
case _ :: t => 1 + length(t)
}
def main(args: Array[String]): Unit = {
println(length(List("a", "b", "c")))
}
}Kaldestakken
Hvert ventende rekursive kald bruger en stakramme. Dyb rekursion samler mange rammer på stakken. For meget store input kan det opbruge stakken og udløse en StackOverflowError.
Fibonacci
Nogle problemer forgrener sig i flere rekursive kald. Fibonacci kalder sig selv to gange, hvilket er elegant, men har eksponentielle omkostninger.
object Main {
def fib(n: Int): Int =
if (n < 2) n
else fib(n - 1) + fib(n - 2)
def main(args: Array[String]): Unit = {
println(fib(10))
}
}Vending af en liste
Rekursion kan opbygge nye strukturer: reverse tilføjer hovedet efter at have vendt halen.
object Main {
def reverse[A](xs: List[A]): List[A] = xs match {
case Nil => Nil
case h :: t => reverse(t) :+ h
}
def main(args: Array[String]): Unit = {
println(reverse(List(1, 2, 3)))
}
}Rekursion kontra iteration
Løkker ændrer en tæller, mens rekursion udtrykker problemet deklarativt. Begge dele er gyldige. Rekursion er velegnet til trælignende data og del-og-hersk, men naiv rekursion risikerer stakoverløb for store lineære input.
Største fælles divisor
Euklids algoritme er naturligt rekursiv og konvergerer hurtigt.
object Main {
def gcd(a: Int, b: Int): Int =
if (b == 0) a else gcd(b, a % b)
def main(args: Array[String]): Unit = {
println(gcd(48, 18))
}
}Hurtigt tjek
Test din grundlæggende forståelse af rekursion.
Opsummering
Du har lært det grundlæggende om rekursion:
- Alle rekursive funktioner har brug for et basistilfælde og et rekursivt tilfælde.
- Hvert ventende kald bruger en stakramme; dyb rekursion kan få stakken til at løbe over.
- Rekursion udtrykker algoritmer for lister og træer naturligt.
Derefter gør du rekursionen sikker for stakken med annoteringen @tailrec.
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
Ofte stillede spørgsmål
Er lektionen “Grundlæggende rekursion” gratis?
Ja — hele teksten til “Grundlæggende rekursion” 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 “Grundlæggende rekursion”?
Rekursive funktioner 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 “Grundlæggende rekursion”?
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
- Grundlæggende rekursion
- tailrec-annotationen
- Akkumulatormønsteret
- Trampolining