Last updated on

Week 1 Debrief: Setup, Recursion exercises

Congratulations on completing your first week of CS-214! Here is a round-up of interesting questions, tips for exercises and labs, and general notes about the course.

Errata

Announcements you might have missed

Administrivia

Interesting links and Ed questions

Deep dives and tips

How to deal with stack overflows and never-ending programs 📘

When dealing with recursive functions, it’s easy to run into an infinite loop and obtain a never-ending test, or an error such as:

java.lang.StackOverflowError
	at factorial(file.scala:9)
	at factorial(file.scala:9)
	at factorial(file.scala:9)
	at factorial(file.scala:9)
	at factorial(file.scala:9)
  ...

This error means that your program exhausted the call stack, a designated memory area where your program stores information about the function currently executing. Every time you make a recursive call, an entry get added to the call stack: if you recurse too deep, it runs out of space, and your program throws a StackOverflowError.

Sometimes, the compiler can optimize away uses of recursion. This is called “tail recursion elimination”; we will study it in week 10.

If you run into this issue, look out for the following points:

  1. Make sure that your function can stop at some point: It needs a base case. For example, the length function stops when encountering an empty list:

    def length(l: IntList): Int =
    if l.isEmpty then 0 // base case, this is where the method stops
    else 1 + length(l.tail) // recursive call

    2025-09-14/code/stackOverflow.worksheet.sc

    Starting to write your recursive method by asking “What happens in this trivial case (0, Nil, etc.)?” can help you think about the whole problem.

  2. Check that the recursive call is decreasing: for the whole function to terminate, each call must get a bit closer to the end of the problem. Here is an obviously bad example:

    def badLength(l: IntList): Int =
    if l.isEmpty then 0
    else 1 + badLength(l) // Woops, nondecreasing call!

    2025-09-14/code/stackOverflow.worksheet.sc

    Sometimes, a function that looks fine may have incorrect behavior for unexpected inputs. What happens if the function below is called on -1?

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

    2025-09-14/code/stackOverflow.worksheet.sc

    There are various strategies in this case. You can extend the scope of the base case:

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

    2025-09-14/code/stackOverflow.worksheet.sc

    … or you can rule out illegal values:

    def factorialRequire(n: Int): Int =
  require(n >= 0, "Illegal negative value passed to factorial.") // check for illegal values
  def rec(n: Int): Int =
    if n == 0 then 1 else n * rec(n - 1)
  rec(n)

    2025-09-14/code/stackOverflow.worksheet.sc

You can use if inside val! 📘

Remember that, in Scala, if is an expression. This means that you can use it in all contexts:

(if b1 then 1 else 2) + (if b2 then 10 else 20)

2025-09-14/code/find.worksheet.sc

val result =
  if x == y then
    println("They are equal!")
    true
  else false
println(result)

2025-09-14/code/find.worksheet.sc

© 2023–2025 EPFL. All rights reserved.