When does the Int count overflow?

An Int is exact through 45 steps (1836311903) and silently wraps to a negative number from 46. Long holds up to 91 steps. Scala BigInt supports + directly, so changing the types to BigInt and the seeds to BigInt(1) gives exact counts for any size.

Is it safe to recurse inside getOrElseUpdate?

With scala.collection.mutable.HashMap in Scala 2.13 and 3, yes: the by-name default is evaluated first and the map rechecks its table before inserting, so keys added by the recursion are not lost. Java's HashMap.computeIfAbsent is different and throws ConcurrentModificationException for the same pattern.

What does @tailrec do?

It asks the compiler to prove that every recursive call is the last operation of the method and to compile it as a loop. If a call is not in tail position, like climbStairs(n - 1) + climbStairs(n - 2), compilation fails instead of silently keeping the recursion.

Could I write the loop with foldLeft instead?

Yes: (1 until n).foldLeft((1, 1)) { case ((prev, curr), _) => (curr, prev + curr) }._2 slides the pair along the range. It reads well but allocates a tuple per step; the @tailrec helper or a while loop with two vars avoids that.

Why no return in these solutions?

Every body is an expression, so its value is the result and return is never needed. A return inside a for or a closure would also be a non-local return, which Scala 3 warns about; when you need to leave a loop early, use boundary and break.

Climbing Stairs in Scala: Recursion, Memo and DP Solutions

climb_stairs.scala

Scala 3.6

Not run yet

+ 7 hidden

Input

n = 4

Expected

The five sequences are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.