Scala – Recursive Functions

In Scala, Recursion is an important concept in pure functional programming language.By definition, Recursive function is a function which calls itself. We need to to be careful while using recursive functions, because program may go into infinite loop if we don’t put a base condition to terminate the program safely.

It is very common to use recursion instead of regular loops like for, while etc. It can take sometime to understand how recursion works but it provides a smarter way to define many algorithms. Let’s understand this with an example. Suppose, we are calculating sum between two numbers. We will create a regular loop for a range between those two numbers and then add the sum for all of them.

Sum between range of two numbers using for loop:

object regularSum {
  def main(args: Array[String]): Unit = {
    def Sum(a: Int, b: Int): Int = {
      if(a>b) 0
      else{
        var result =0
        for(num <- a to b){
          result += num
        }
        result
      }
    }

    val totalSum =Sum(1,5)   //Calling Sum Function
    print(totalSum)
  }
}

Output: 15

Now, above function can also be written as recursive function which will provide the same result.

object regularSum {
  def main(args: Array[String]): Unit = {
    def recursiveSum(a: Int, b: Int): Int = {
      if(a>b) 0
      else{
        a+recursiveSum(a+1,b)      }
    }

    val totalSum =recursiveSum(1,5)   //recursive call Sum Function
    print(totalSum)
  }
}

Output:15

Now, here is a point to learn, that if we pass a large number e.g. 55555 in the above program, it will throw an error as java.lang.StackOverflowError. Because it is adding the numbers for the given range for every function and leave the value on stack using some memory every time.So, when stack is full we get the above error.

Tail Recursion:

As an optimal approach and specially for larger values , tail recursion can be proved better as tail recursion can be optimised by compiler. Tail recursion is a function where the last action in the function is the recursive call to the function itself. It can resolve the stackOverflowError, because there is no need to keep the record of the previous state. Let’s see with an example.

Below is the non-tail recursive function which accepts List as an arguments and sum up the values of the list.

object regularSum {
  def main(args: Array[String]): Unit = {
    def sum(is: List[Int]): Int = is match {
      case x :: y => x + sum(y)
      case _      => 0
    }
    print(sum(List.range(1,6)))
  }
}

Output: 15

We can make sure that function is non-tail recursive by providing @tailrec annotation . It will throw error and tell us that function is not tail recursive. It will give the compile time error.

object regularSum {
  def main(args: Array[String]): Unit = {
    @tailrec
    def sum(is: List[Int]): Int = is match {
      case x :: y => x + sum(y)
      case _      => 0
    }
    print(sum(List.range(1,6)))
  }
}

Output: Error:(10, 22) could not optimize @tailrec annotated method sum: it contains a recursive call not in tail position
      case _      => 0

When we provide a large value in the above function, it throws the stackOverflowError as we have seen before.So, to create a tail recursive function , we define 2 functions having and 2nd function will one more parameter ‘acc’. We will call the second function from the first function and recursive call should be the last call in the second function.

object regularSum {
  def main(args: Array[String]): Unit = {
    def sum(ls: List[Int]): Int = {

      @tailrec
      def SumAcc(cur: List[Int], acc: Int): Int = cur match {
        case x :: y => SumAcc(y, acc + x)
        case _      => acc
      }

      SumAcc(ls, 0)
    }
    print(sum(List.range(1,55555)))
  }
}