Scala for Backend Engineering & Functional Programming · Lesson

Thinking Recursively

Base cases and recursive steps.

Thinking Recursively is a free Scala for Backend Engineering & Functional Programming lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Scala for Backend Engineering & Functional Programming learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

What Recursion Means

Recursion is when a function calls itself to solve a smaller version of the same problem.

In Scala, recursion is a natural fit for functional programming because it lets you express loops without mutable variables.

Every recursive function needs two things: a way to stop, and a way to shrink the problem.

Base Case First

The base case is the simplest input the function can answer directly, with no further recursion.

Without a base case, the function would call itself forever and crash with a stack overflow.

Always design the base case before the recursive step.

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

A First Recursive Function

Here is a complete program that sums the numbers from 1 to n.

The base case returns 0; the recursive case adds n to the sum of everything below it.

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

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

Tracing the Calls

To understand recursion, expand the calls by hand.

sum(3) becomes 3 + sum(2), which becomes 3 + 2 + sum(1), then 3 + 2 + 1 + sum(0).

Only when sum(0) returns 0 does the chain collapse back into a single value: 6.

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

Recursion on Lists

Lists are recursive by nature: a list is either empty (Nil) or a head followed by a smaller tail.

This shape maps directly onto recursive functions. The empty list is the base case; the head plus recursion on the tail is the recursive step.

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

Pattern Matching the Tail

The :: pattern splits a non-empty list into its head and tail.

Each recursive call works on a strictly shorter list, guaranteeing progress toward Nil.

This is the canonical way to walk a list recursively in 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

Two Recursive Calls

Some problems branch into more than one recursive call.

The classic example is Fibonacci, where each value depends on the two before it.

This naive version is simple but slow, because it recomputes the same values many times.

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

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

The Stack Cost

Each recursive call adds a frame to the call stack, which must wait for the inner call to return.

For very deep recursion, this can exhaust the stack and throw a StackOverflowError.

Counting depth, not just size, helps you predict this risk.

// 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

Shrinking Toward the Base

The key invariant of recursion is that every call must move closer to the base case.

If the argument does not get smaller, or never reaches the stopping condition, the recursion never ends.

Check this before running anything.

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

Recursion vs Loops

Imperative code uses while loops with mutable counters; functional code uses recursion with immutable values.

Both can express the same computations, but recursion describes the structure of the data more directly.

In Scala, you will often prefer recursion or higher-order functions over raw loops.

// 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)

Designing a Recursive Solution

A reliable recipe: identify the base case, assume the recursive call already works on the smaller input, then combine the head with that result.

This leap of faith is the heart of recursive thinking. You trust the smaller call and only handle one step.

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

Quick Check

Test your understanding of recursive structure.

Recap

Recursion solves a problem by reducing it to a smaller instance of itself.

Every recursive function needs a base case to stop and a recursive step that shrinks the input toward that base.

Lists, with their Nil and head-tail shape, are an ideal playground for recursive thinking. Watch the stack depth on very large inputs.

Frequently asked questions

Is the “Thinking Recursively” lesson free?

Yes — the full text of “Thinking Recursively” is free to read here on the web, and the Scala for Backend Engineering & Functional Programming course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Scala for Backend Engineering & Functional Programming course, upgrade to CoddyKit PRO.

What will I learn in “Thinking Recursively”?

Base cases and recursive steps. You practise Scala for Backend Engineering & Functional Programming with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start Scala for Backend Engineering & Functional Programming?

No prior experience is required. Scala for Backend Engineering & Functional Programming on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Thinking Recursively” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this Scala for Backend Engineering & Functional Programming lesson?

Yes. Every Scala for Backend Engineering & Functional Programming lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

← Back to Scala for Backend Engineering & Functional Programming