Find Factorial of a Number in Scala

1. Introduction

The factorial of a positive number, denoted by the symbol n!, is obtained by multiplying all integers from one to the given number, represented by n. The formula for factorial is n * (n-1) * … * 2 * 1. Moreover, it’s important to note that the factorial for 0 is defined as 1, whereas for negative numbers, it is not defined.

In this tutorial, we’ll look at different ways to calculate the factorial of a number in Scala.

2. Using Recursion

The most common and popular way to calculate the factorial is using recursion. Let’s look at the implementation using a simple recursive approach:

def factorialUsingRecursion(num: Int): BigInt = {
  require(num >= 0, "Factorial is not defined for negative numbers")
  if (num == 0) 1
  else num * factorialUsingRecursion(num - 1)
}

Here, we recursively compute the factorial of a given number using the factorialUsingRecursion() function. Additionally, a require() statement is included to enforce that the factorial calculation is valid only for non-negative numbers. Notice that we are utilizing BigInt to avoid numeric overflows on large factorials.

3. Using Tail Recursion

Recursion can occasionally lead to stack overflow issues, particularly when dealing with large numbers. However, Scala offers an optimized version of recursion known as tail recursion. Let’s reimplement the previous recursive solution using the tail-recursive approach:

def factorialUsingTailRecursion(num: Int): BigInt = {
  require(num >= 0, "Factorial is not defined for negative numbers")
  @tailrec
  def fac(n: Int, acc: BigInt): BigInt = {
    n match {
      case 0   => acc
      case num => fac(num - 1, acc * num)
    }
  }
  fac(num, BigInt(1))
}

In this implementation, we calculated the factorial using tail recursion, which helps prevent stack overflow errors.

4. Using product()

Scala defines the product() method for all numeric collections. This method computes the product of all numbers within the given collection. To compute the factorial of a given number, we can generate a range and then apply the product() method to it:

def factorialUsingProduct(num: Int): BigInt = {
  require(num >= 0, "Factorial is not defined for negative numbers")
  num match {
    case 0 => BigInt(1)
    case _ => (BigInt(1) to BigInt(num)).product
  }
}

In this approach, we introduced a dedicated condition to handle the factorial of 0 and utilized the product() method for other positive numbers.

5. Using reduce()

Another approach to calculating the factorial is by using the reduce() method on the range:

def factorialUsingReduce(num: Int): BigInt = {
  require(num >= 0, "Factorial is not defined for negative numbers")
  num match {
    case 0 => BigInt(1)
    case _ => (BigInt(1) to BigInt(num)).reduce(_ * _)
  }
}

Similar to the product() implementation, we’re utilizing the range to generate a series of numbers.

Since multiplication is associative, we can also use reduceLeft() or reduceRight() in place of reduce().

6. Conclusion

In this short article, we explored multiple ways to calculate the factorial of a given number. While the recursive solution offers simplicity and elegance, the tail-recursive implementation optimizes performance and avoids stack overflow issues, especially for large numbers. On the other hand, functional methods such as product() and reduce() leverage the power of Scala’s collections library, providing concise and efficient solutions.

As always, the sample code shown here is available over on GitHub.