Scala Recursion

Recursion is when a function calls itself to solve a problem. Instead of writing a loop that counts down, you write a function that calls itself with a smaller version of the problem until it reaches a base case — a simple scenario that has a direct answer. Functional programming favors recursion because it avoids mutable state.

The Recipe for Recursion

Every recursive function needs two things:

1. Base case   — the simplest version, answered directly (no self-call)
2. Recursive case — break the problem into a smaller piece, then call self

Factorial

def factorial(n: Int): Int =
  if n <= 1 then 1                    // base case
  else n * factorial(n - 1)           // recursive case

println(factorial(5))   // 120

factorial(5)
  = 5 * factorial(4)
        = 4 * factorial(3)
              = 3 * factorial(2)
                    = 2 * factorial(1)
                          = 1          ← base case
              = 2 * 1 = 2
        = 3 * 2 = 6
  = 4 * 6 = 24
= 5 * 24 = 120

Fibonacci

def fibonacci(n: Int): Int =
  if n == 0 then 0
  else if n == 1 then 1
  else fibonacci(n - 1) + fibonacci(n - 2)

for i <- 0 to 9 do print(s"${fibonacci(i)} ")
// 0 1 1 2 3 5 8 13 21 34

                fibonacci(4)
               /             \
         fib(3)             fib(2)
        /      \            /     \
     fib(2)  fib(1)     fib(1)  fib(0)
     /    \
  fib(1) fib(0)

Warning: this naive implementation recalculates the same values many times. fibonacci(40) is already slow. For large values, use memoization (caching) or the iterative approach.

Sum of a List

def sumList(nums: List[Int]): Int =
  nums match
    case Nil          => 0                          // base: empty list
    case head :: tail => head + sumList(tail)       // recursive: add head, recurse on tail

println(sumList(List(1, 2, 3, 4, 5)))   // 15

sumList(List(1, 2, 3))
= 1 + sumList(List(2, 3))
      = 2 + sumList(List(3))
            = 3 + sumList(Nil)
                  = 0
      = 3 + 0 = 3
= 2 + 3 = 5
= 1 + 5 = 6

Power Function

def power(base: Int, exp: Int): Long =
  if exp == 0 then 1L
  else base * power(base, exp - 1)

println(power(2, 10))   // 1024
println(power(3, 5))    // 243

Counting Down

def countdown(n: Int): Unit =
  if n <= 0 then println("Blast off!")
  else
    println(n)
    countdown(n - 1)

countdown(5)
// 5
// 4
// 3
// 2
// 1
// Blast off!

Reverse a List

def reverseList[A](list: List[A]): List[A] =
  list match
    case Nil          => Nil
    case head :: tail => reverseList(tail) :+ head

println(reverseList(List(1, 2, 3, 4)))   // List(4, 3, 2, 1)

GCD (Greatest Common Divisor)

def gcd(a: Int, b: Int): Int =
  if b == 0 then a else gcd(b, a % b)

println(gcd(48, 18))   // 6
println(gcd(100, 75))  // 25

gcd(48, 18) = gcd(18, 48 % 18) = gcd(18, 12)
            = gcd(12, 18 % 12) = gcd(12, 6)
            = gcd(6, 12 % 6)   = gcd(6, 0)
            = 6

Stack Overflow Risk

Each recursive call uses a stack frame. Too many calls exhaust the call stack:

// This will crash with StackOverflowError for large n
def countDown(n: Int): Unit =
  if n > 0 then countDown(n - 1)

countDown(100000)   // StackOverflowError!

The solution is tail recursion, covered in the next topic. A tail-recursive function does not keep stack frames — it reuses the same frame, allowing unlimited recursion depth.

Recursion vs While Loop

// Recursive — functional style
def sum(n: Int): Int = if n <= 0 then 0 else n + sum(n - 1)

// While loop — imperative style
def sumLoop(n: Int): Int =
  var total = 0
  var i = n
  while i > 0 do { total += i; i -= 1 }
  total

// Collection method — most idiomatic Scala
def sumCol(n: Int): Int = (1 to n).sum

Recursion shines when the problem has a naturally recursive structure — trees, nested data, mathematical sequences. For simple counting or accumulation, collection methods are shorter and stack-safe.