Scala for Backend Engineering & Functional Programming · Lesson

Recursion Basics

Recursive functions.

Recursion Basics 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 is Recursion?

Recursion is when a function calls itself to solve a smaller version of the same problem. It is a natural fit for functional programming, replacing many loops with self-referential definitions.

Two Essential Parts

Every correct recursive function needs:

A base case that stops the recursion.
A recursive case that moves toward the base case.

Without a reachable base case, recursion runs forever.

Factorial

The classic example: n! = n * (n-1)!, with 0! = 1 as the base case.

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

Tracing the Calls

Each recursive call pauses and waits for the inner result. factorial(3) expands to 3 * (2 * (1)). The multiplications happen as the calls return.

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 of a List

Recursion over a list: the sum is the head plus the sum of the tail, with the empty list summing to zero.

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

Length of a List

The same pattern computes length: empty is 0, otherwise 1 plus the length of the tail.

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")))
  }
}

The Call Stack

Each pending recursive call uses a stack frame. Deep recursion stacks many frames. For very large inputs, this can exhaust the stack and throw a StackOverflowError.

Fibonacci

Some problems branch into multiple recursive calls. Fibonacci calls itself twice, which is elegant but exponential in cost.

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

Reversing a List

Recursion can build new structures: reverse appends the head after reversing the tail.

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

Recursion vs Iteration

Loops mutate a counter; recursion expresses the problem declaratively. Both are valid. Recursion shines for tree-shaped data and divide-and-conquer, but naive recursion risks stack overflow for large linear inputs.

Greatest Common Divisor

Euclid's algorithm is naturally recursive and converges quickly.

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

Quick Check

Test your recursion fundamentals.

Recap

You learned recursion basics:

Every recursive function needs a base case and a recursive case.
Each pending call uses a stack frame; deep recursion can overflow.
Recursion expresses list and tree algorithms naturally.

Next, you will make recursion stack-safe with the @tailrec annotation.

Frequently asked questions

Is the “Recursion Basics” lesson free?

Yes — the full text of “Recursion Basics” 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 “Recursion Basics”?

Recursive functions. 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 “Recursion Basics” 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