Learning Functional Data Structures and Algorithms

Recursion aids immutability

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 ...