Grunderna i rekursion
Rekursiva funktioner.
Grunderna i rekursion är en gratis lektion i Scala för backendutveckling och funktionell programmering på CoddyKit. Detta är lektion 1 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Scala för backendutveckling och funktionell programmering, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Scala för backendutveckling och funktionell programmering innehåller totalt 4 lektioner.
Vad är rekursion?
Rekursion innebär att en funktion anropar sig själv för att lösa en mindre version av samma problem. Det passar naturligt för funktionell programmering och ersätter många loopar med självrefererande definitioner.
Två viktiga delar
Varje korrekt rekursiv funktion behöver:
- Ett basfall som stoppar rekursionen.
- Ett rekursivt fall som närmar sig basfallet.
Utan ett basfall som kan nås fortsätter rekursionen för evigt.
Fakultet
Det klassiska exemplet: n! = n * (n-1)!, där 0! = 1 är basfallet.
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))
}
}Följ anropen
Varje rekursivt anrop pausar och väntar på det inre resultatet. factorial(3) utvecklas till 3 * (2 * (1)). Multiplikationerna utförs när anropen returnerar.
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))
}
}Summan av en lista
Rekursion över en lista: summan är huvudet plus summan av svansen, där en tom lista har summan noll.
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 på en lista
Samma mönster beräknar längden: en tom lista har längden 0, annars är längden 1 plus svansens längd.
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")))
}
}Anropsstacken
Varje väntande rekursivt anrop använder en stackram. Djup rekursion lägger många stackramar på varandra. För mycket stora indata kan detta tömma stacken och kasta ett StackOverflowError.
Fibonacci
Vissa problem förgrenar sig i flera rekursiva anrop. Fibonacci anropar sig själv två gånger, vilket är elegant men har exponentiell kostnad.
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))
}
}Vända en lista
Rekursion kan bygga nya strukturer: reverse lägger huvudet sist efter att svansen har vänts.
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 jämfört med iteration
Loopar ändrar en räknare, medan rekursion uttrycker problemet deklarativt. Båda är giltiga. Rekursion passar särskilt bra för trädformade data och divide-and-conquer, men naiv rekursion riskerar stackspill för stora linjära indata.
Största gemensamma delare
Euklides algoritm är naturligt rekursiv och konvergerar snabbt.
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))
}
}Snabbtest
Testa Era grunder i rekursion.
Sammanfattning
Ni har lärt Er rekursionens grunder:
- Varje rekursiv funktion behöver ett basfall och ett rekursivt fall.
- Varje väntande anrop använder en stackram; djup rekursion kan orsaka stackspill.
- Rekursion uttrycker algoritmer för listor och träd på ett naturligt sätt.
Härnäst gör Ni rekursion stack-säker med annoteringen @tailrec.
Lär dig Scala med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 39
- Lektioner
- 143
Vanliga frågor
Är lektionen ”Grunderna i rekursion” gratis?
Ja – hela texten till ”Grunderna i rekursion” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Scala för backendutveckling och funktionell programmering, kan Ni uppgradera till CoddyKit PRO. Kursen i Scala för backendutveckling och funktionell programmering innehåller totalt 4 lektioner.
Vad lär jag mig i ”Grunderna i rekursion”?
Rekursiva funktioner. Ni övar på Scala för backendutveckling och funktionell programmering med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Scala för backendutveckling och funktionell programmering?
Du behöver inga förkunskaper. Utbildningen i Scala för backendutveckling och funktionell programmering på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.
Hur lång tid tar lektionen ”Grunderna i rekursion”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Scala för backendutveckling och funktionell programmering-lektionen?
Ja. Varje Scala för backendutveckling och funktionell programmering-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Grunderna i rekursion
- Annotationen tailrec
- Ackumulatormönstret
- Trampolining