What recursion is
A recursive method solves a problem by calling itself on a smaller version of the same problem. Every recursive method has two parts:
- a base case, an input small enough to answer directly, without another call;
- a recursive case, which reduces the input and combines the result of the smaller call into the answer.
Without a base case, the calls never stop. With a recursive case that doesn't shrink the input, they don't reach the base case either. Either way the program eventually fails with a StackOverflowError, because every active call occupies space on the call stack.
Recursion fits problems whose answer is naturally built from the answer to a smaller piece: factorials, tree traversals, divide and conquer, and backtracking. In this chapter you will use it to compute values, search and explore.
The factorial
For a non-negative integer n, n! is the product 1 * 2 * 3 * ... * n. For example, 5! = 120. The definition contains a smaller copy of itself:
n! = n * (n - 1)!
0! = 1
The second line is the base case, and the first is the recursive case. Each call asks for the factorial of a number one smaller, so after n calls it reaches 0.
The exercise, step by step
The method factorial(n: Int): Int takes a non-negative n and returns n!. The expected cost is O(n) time and O(n) extra space, which matches n calls waiting on the stack.
- Base case: if
n == 0, return1. This answers the smallest input directly and stops the recursion. - Recursive case: return
factorial(n - 1) * n. The call hands a smaller problem to the next level, and the result is multiplied bynon the way back.
class Solution {
def factorial(n: Int): Int = {
if (n == 0) {
return 1
}
return factorial(n - 1) * n
}
}
How the calls unfold
For factorial(3), the call goes down to the base case, and then the multiplications happen while the calls return. Printing each call (indented by depth) and each result as it comes back shows the order:
factorial(3)
factorial(2)
factorial(1)
factorial(0)
-> 1
-> 1
-> 2
-> 6
Nothing is multiplied until factorial(0) returns 1. Then factorial(1) computes 1 * 1, factorial(2) computes 1 * 2 and factorial(3) computes 2 * 3.
Recursion in Scala: what to know
Recursive methods need a declared result type
Scala can usually infer a method's return type, but for a method that calls itself it can't, so you must write it: def factorial(n: Int): Int. The starting code already does.
return is optional
The value of a method is its last expression, so the same method can be written without any return:
def factorial(n: Int): Int =
if (n == 0) 1 else factorial(n - 1) * n
In Scala, if / else is an expression and produces a value, which makes short recursive definitions like this one natural. The lesson uses the explicit return form, and both versions behave identically.
Int overflows quickly
An Int is 32 bits and overflow wraps silently. Factorials grow fast: factorial(12) is 479001600, the largest one that fits. factorial(13) returns 1932053504 instead of 6227020800, with no error. A Long version goes further, up to 20! (2432902008176640000), and 21! wraps there too, giving -4249290049419214848.
Stack depth is limited
Every call waits for the one below it, so n calls are open at once. The JVM's stack is finite. A recursion that is only 1,000 calls deep is fine, but one that is 100,000 deep, such as a simple counting recursion if (n == 0) 0 else 1 + deep(n - 1) called with 100000, ends in a StackOverflowError with the default stack size. For this lesson, small inputs are enough. A call such as factorial(-1) also ends in a StackOverflowError, because the input moves away from 0 instead of toward it.
Tail recursion
If the recursive call is the very last thing a method does, nothing is left to do after it returns, and Scala can compile that into a loop. You can ask the compiler to check this with the @tailrec annotation from scala.annotation.tailrec:
import scala.annotation.tailrec
def factorialTail(n: Int): Long = {
@tailrec
def go(k: Int, acc: Long): Long =
if (k == 0) acc else go(k - 1, acc * k)
go(n, 1L)
}
Here the running product travels in the extra parameter acc, so the multiplication happens before the call and not after it. The version in the lesson, factorial(n - 1) * n, is not tail-recursive, because the multiplication is still pending when the call returns. That is why it uses O(n) stack space.
Loop or recursion
Factorial can also be written with a loop:
var result = 1
for (i <- 1 to n) {
result *= i
}
Both give the same numbers. The loop uses O(1) space. Recursion becomes more valuable when the problem splits into several smaller problems, where a loop is awkward to write.
Key takeaways
- A recursive method needs a base case and a recursive case that moves toward it.
- For factorial, the base case is
n == 0returning 1, and the recursive case isfactorial(n - 1) * n. - Scala requires an explicit result type on a recursive method.
- The last expression is the result, so
returnis optional. - Deep recursion uses stack space, and missing base cases end in a
StackOverflowError. - With
Int, factorials overflow silently after12!.
