🎓 A1Learner
🔍
0 of 50 lessons completed

Scala Recursion

Recursion is when a function calls itself to work on a smaller piece of the same problem. Each call gets closer to a case so simple that the function can answer it directly.

A countdown that stops at zero

countdown prints its number and then calls itself with one less. When n reaches zero, the condition fails and the calls stop.

def countdown(n: Int): Unit =
  if n > 0 then
    println(n)
    countdown(n - 1)

@main def main(): Unit =
  countdown(3)

Factorial built from smaller factorials

The factorial of a number is that number times the factorial of one less. The stopping case is 1, whose factorial is 1.

def factorial(n: Int): Int =
  if n <= 1 then
    1
  else
    n * factorial(n - 1)

@main def main(): Unit =
  println(factorial(5))
  println(factorial(3))
  println(factorial(1))

A recursive sum over a list

sumList adds the head of the list to the sum of the tail, which a self call works out. The stopping case is the empty list, whose sum is zero.

def sumList(xs: List[Int]): Int =
  if xs.isEmpty then
    0
  else
    xs.head + sumList(xs.tail)

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

Example

def sumTo(n: Int): Int =
  if n <= 0 then
    0
  else
    n + sumTo(n - 1)

@main def main(): Unit =
  println(sumTo(4))
  println(sumTo(10))
  println(sumTo(0))

Key points

  • Recursion: A recursive function is a function that calls itself inside its own body.
  • Stopping case: The stopping case is the simple input for which the function answers directly, without calling itself.
  • Smaller input: Every self call must pass a smaller input, so the calls move toward the stopping case.
  • Unwinding: When the stopping case is reached, the waiting calls finish one by one and build the final result.
  • List recursion: A list problem can handle the head alone and let a self call handle the tail.

In this example, sumTo adds all the whole numbers from n down to 1 by calling itself with one less each time. The stopping case gives back 0 when n reaches zero, as the last call shows. The waiting calls then add up, so sumTo(4) gives 10 and sumTo(10) gives 55.

Note

Without a stopping case, a recursive function would call itself forever and never finish.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Scastie

Exercise

With a factorial def that stops at 1 and otherwise gives back n * factorial(n - 1), what does factorial(4) give back?