Instead of writing a loop using a mutable loop variable, functional languages advocate recursion as an alternative. Recursion is a widely used technique in imperative programming languages, too. For example, quicksort and binary tree traversal algorithms are expressed recursively. Divide and conquer algorithms naturally translate into recursion.
When we start writing recursive code, we don't need mutable loop variables:
scala> import scala.annotation.tailrec
import scala.annotation.tailrec
scala> def factorial(k: Int): Int = {
| @tailrec
| def fact(n: Int, acc: Int): Int = n match {
| case 1 => acc
| case _ => fact(n-1, n*acc)
| }
| fact(k, 1)
| }
factorial: (k: Int)Int
scala> factorial(5)
res0: Int = 120
Note the @tailrec annotation. Scala gives us an option to ensure that tail call optimization (TCO) is applied. TCO rewrites a recursive tail call as a loop. So in reality, no stack frames are used; this eliminates the possibility of a stack overflow error.
Here is the equivalent Clojure code:
user=> (defn factorial [n] #_=> (loop [cur n fac 1] #_=> (if (= cur 1) #_=> fac #_=> (recur (dec cur) (* fac cur) )))) #'user/factorial user=> (factorial 5) 120
The following diagram shows how recursive calls use stack frames:
Clojure's special form, recur, ensures that the TCO kicks in.
Note how these versions are starkly different than the one we would write in an imperative paradigm.
Instead of explicit looping, we use recursion so we wouldn't need to change any state, that is, we wouldn't need any mutable variables; this aids immutability.