Recursion

Recursion occurs when a method or function calls itself. The scary thing about this to the uninitiated is how easy it is to create an infinite loop that just goes round and round calling itself.

Once you get used to it recursion becomes really powerful and is an important part of the Scala programmer’s toolkit. It is especially useful when dealing with collections – part of functional programming is about avoid temporary variables such as those often found in for loops.

Recursion is not specific to functional programming but is used a great deal. For instance, the ‘Hello World’ of any functional programming language is the function ‘factorial’.

def factorial(n: Int): Int = n match {
  case 0 => 1
  case other => other * factorial(other - 1)
}

This is one of the simpler recursive methods, often a recursive function in Scala will have an outer and inner function – the outer one being the ‘public’ method creating initial values for the inner function, calling it and then returning the answer from it:

def length[A](seq: Seq[A]): Int = {
  @tailrec
  def _len(seqInner: Seq[A], n: Int = 0): Int = seqInner match {
    case Nil => n
    case head :: tail => _len(tail, n + 1)
  }
  _len(seq)
}

Here the outer function length just delegates to the inner function. The two main things to note in this example are the @tailrec annotation and the n parameter to the inner function.

The @tailrec annotation indicates that the developer assumes that the compiler will perform a certain optimization. If the compiler is unable to perform this it will produce a warning to make the developer aware. The optimization will be converting the call to a while loop behind the scenes. Tail recursion is a bigger topic than I can do justice and hopefully the subject of a subsequent post.

The n parameter has a default value meaning the outer function need not pass it but recursive calls may.

Simple Binary Search Tree in Scala

This class is a bit more involved than I usually post, and it’s only a bare bones BST with 3 methods –

trait BareBonesBinarySearchTree {
  def insert(key:Int)
  def has(key:Int):Boolean
  def inOrderTraversal():Unit
}
/** Simple implementation of a Binary Search Tree. */
class BinarySearchTree {

  /* Our Root Node. Empty to start with. */
  var rootNode: Option[Node] = None

  /* Inserts a value i if it does not already exist. */
  def insert(i: Int) = {

    /* Require optimization or a warning. */
    @tailrec
    def findSuitableParent(i: Int, o: Option[Node], p: Option[Node]): Option[Node] = {
      o match {
        case None => return p
        case Some(n) if (n.key > i) => findSuitableParent(i, n.left, o)
        case Some(n) if (n.key < i) => findSuitableParent(i, n.right, o)
        case Some(n) if (n.key == i) => None
      }
    }

    /* Check for a root node, if none make this the root node else find a parent. */
    rootNode match {
      case None => rootNode = Some(Node(i))
      case Some(node) => {
        val p = findSuitableParent(i, rootNode, None);
        p match {
          case None => // duplicate
          case Some(n) if (n.key > i) => n.left = Some(Node(key = i, parent = p))
          case Some(n) if (n.key < i) => n.right = Some(Node(key = i, parent = p))
        }
      }
    }
  }

  /* Function returning whether a given value exists. */
  def has(i: Int): Boolean = {
    @tailrec
    def _has(value: Int, oNode: Option[Node], seen: List[Node]): Boolean = {
      oNode match {
        case None => return false
        case Some(node) if (node.key == value) => return true;
        case Some(node) if (node.key > value) => _has(value: Int, node.left, node :: seen)
        case Some(node) if (node.key < value) => _has(value: Int, node.right, node :: seen)
      }
    }

    /* Is there a root node? If not then we don't have value i else traverse and locate. */
    rootNode match {
      case None => return false
      case Some(node) => return _has(i, rootNode, List())
    }
  }

  def inOrderTraversal = {
	/* Look left of current node then look at node then look right. */
    def _traverse(n: Option[Node]): Unit = {
      n match {
        case None =>
        case Some(node) => _traverse(node.left); println("This node: " + node.key); _traverse(node.right)
      }
    }
    /* Starting at root node. */
    _traverse(rootNode)
  }
}

case class Node(key: Int, var left: Option[Node] = None, var right: Option[Node] = None,
  var parent: Option[Node] = None)

A part of the JUnit test class is here:

import junit.framework.TestCase
import org.junit.Test
import junit.framework.Assert
import scala.annotation.tailrec

class BinarySearchTreeTest extends TestCase {

  var tree: BinarySearchTree = _

  override def setUp = {
    tree = new BinarySearchTree
  }

  @Test
  def testAddTwoHighLowOneNotExist = {
    tree.insert(50)
    tree.insert(47)
    Assert.assertTrue(tree.has(47))
    Assert.assertTrue(tree.has(50))
    Assert.assertFalse(tree.has(51))
  }
}

Function Composition in Scala

package com.vff.lessons

/** Example of composing a function from 2 existing functions. */
object FunctionComposition extends App {

  /* Define the two functions. */
  val less1: Int => Int = _ - 1
  val times2: Int => Int = _ * 2
  val times3: Int => Int = _ * 3

  /* Compose a function from both but note the order: */
  val less1times3 = less1 compose times3

  /* Output result. */
  println("17 times 3 less 1 = " + less1times3(17))
}

Output:

17 times 3 less 1 = 50