Scala - Recursion Functions

---

---

Recursion is a technique in which a function calls itself in order to solve a problem. Recursion is used as an alternative to iteration for tasks like traversing data structures, performing calculations, and solving complex problems.

Recursive Functions

Recursive function is a function that calls itself in its definition. Recursive functions call themselves to solve a problem by breaking down a big problem into smaller sub-problems. Recursion can be direct and indirect. Direct recursion occurs when the function calls itself directly. Indirect recursion occurs when the function calls another function that eventually calls the original function.

Basic Concept

Recursive function is defined similarly to a regular function, but it calls itself. So recursive functions must have a base case to prevent infinite recursion and stop. There are two parts of recursive functions:

• Base Case: Function stops calling itself to prevent infinite recursion.
• Recursive Case: Function calls itself with modified arguments and moves towards the base case.

Factorial: Example of Recursive Function

The factorial of a non-negative integer n is the product of all positive integers less than or equal to n. It can be defined recursively as:

• factorial(0) = 1 (base case)
• factorial(n) = n * factorial(n - 1) (recursive case)

Syntax

The syntax of recursive function is -

def functionName(parameters): ReturnType = {
  if (baseCondition) {
    // base case
    baseResult
  } else {
    // recursive case
    functionName(modifiedParameters)
  }
}

Example

The following example shows a simple recursive function to calculate the factorial of a number -

def factorial(n: Int): Int = {
  if (n == 0) 1  // base case
  else n * factorial(n - 1)  // recursive case
}

object Demo {
  def main(args: Array[String]) = {
    println("Factorial of 5: " + factorial(5))
  }
}

Save the above program in Demo.scala. The following commands are used to compile and execute this program.

Command

> scalac Demo.scala
> scala Demo

Output

Factorial of 5: 120

In the example, the factorial function calculates the factorial of a given number n. The function uses base case (n == 0) to return 1. The recursive case (n * factorial(n - 1)) to multiply n by the factorial of n - 1. 

Tail Recursion

Tail recursion is a special form of recursion where the recursive call is the last operation in the function. Since there is no advantage of tail recursive function over iterative function. So

Tail-recursive functions are optimized by the Scala compiler to prevent stack overflow and improve performance.

Syntax

Tail-recursive function can be defined using the @tailrec annotation. It ensures that the function is optimized by the compiler.

import scala.annotation.tailrec

@tailrec
def functionName(parameters): ReturnType = {
  if (baseCondition) {
    // base case
    baseResult
  } else {
    // recursive case
    functionName(modifiedParameters)
  }
}

Example

The following example shows a tail-recursive function to calculate the factorial of a number -

import scala.annotation.tailrec

def factorial(n: Int): Int = {
  @tailrec
  def factorialHelper(x: Int, accumulator: Int): Int = {
    if (x == 0) accumulator
    else factorialHelper(x - 1, x * accumulator)
  }
  factorialHelper(n, 1)
}

object Demo {
  def main(args: Array[String]) = {
    println("Factorial of 5: " + factorial(5))
  }
}

Save the above program in Demo.scala. The following commands are used to compile and execute this program.

Command

> scalac Demo.scala
> scala Demo

Output

Factorial of 5: 120

In the example, the factorial function has helper function factorialHelper. It is tail-recursive. The factorialHelper function takes parameter accumulator to accumulate the result. The @tailrec annotation ensures that the function is optimized by the Scala compiler.

Recursion vs Iteration

These are some differences between recursive and iterative programs in Scala -

Example: Sum of Natural Numbers

Both recursion and iteration can be used to calculate the sum of the first n natural numbers in Scala -

Recursive

def sum(n: Int): Int = {
  if (n == 0) 0
  else n + sum(n - 1)
}

object Demo {
  def main(args: Array[String]) = {
    println("Sum of first 5 natural numbers: " + sum(5))
  }
}

Iterative

def sum(n: Int): Int = {
  var total = 0
  for (i <- 1 to n) {
    total += i
  }
  total
}

object Demo {
  def main(args: Array[String]) = {
    println("Sum of first 5 natural numbers: " + sum(5))
  }
}

Save the above program in Demo.scala. The following commands are used to compile and execute this program.

Command

> scalac Demo.scala
> scala Demo

Output

Sum of first 5 natural numbers: 15

In the recursive version, the sum function calculates the sum of the first n natural numbers using a base case (n == 0) to return 0. Recursive case (n + sum(n - 1)) to add n to the sum of n - 1 numbers.

In the iterative version, the sum function calculates the sum using a for loop to iterate through the numbers from 1 to n. So, accumulating the total in the total variable.

Recursive Function Summary

• Recursive functions in Scala call themselves to solve problems. Recursive functions break down a big problem into smaller sub-problems.
• Recursive functions can be used to traverse and manipulate data structures, like lists and trees.
• Tail recursion is a special case of recursion where the recursive call is the last operation. So optimization and preventing stack overflow errors.
• Recursive functions have advantages in simplicity and modularity. But can have disadvantages in performance and risk of stack overflow.