O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required