Pattern 12Tail Recursion


To repeat a computation without using mutable state and without overflowing the stack


Iteration is an imperative technique that requires mutable state. For example, let’s examine a trivial problem, writing a function that will calculate the sum from one up to an arbitrary number, inclusive. The code below does just that, but it requires both i and sum to be mutable:

public​ ​static​ ​int​ sum(​int​ upTo) {
int​ sum = 0;
for​ (​int​ i = 0; i <= upTo; i++)
sum += i;
return​ sum;

Since the functional world emphasizes immutability, iteration is out. In its place, we can use recursion, which does not require immutability. ...

Get Functional Programming Patterns in Scala and Clojure now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.