Simple Scala recursion examples (recursive programming)

As I’ve been learning more about Scala and functional programming, I’ve been looking at accomplishing more tasks with recursive programming techniques. As part of my studies I put together a number of Scala recursion examples below, including:

  • Sum
  • Product
  • Max
  • Fibonacci
  • Factorial

I won’t write too much about recursion theory today, just some basic thoughts. I’ll come back here and add more when I have some good thoughts or better examples to share.

Back to top

Thinking in recursion

When I’m going to write a recursive method, I usually think about it like this:

  • I know I want to do something with a collection of data elements.
  • Therefore, my function will usually take this collection as an argument.
  • Within the function I usually have two branches:
    • In one case, when I’m handling the situation of being at the last element of the collection, I do some “ending” operation. For instance, in the Sum example below, when I get to the Nil element in a List, I return 0 and let the recursive method calls unroll.
    • In the second case, as when the function is not at the end of the list, I write the code for my main algorithm; it operates on the current element in the collection (the ’head’ element); I then recursively call my function, passing it the remainder of the collection (the ’tail’).
  • When the function calls unroll, the function returns whatever it is that I’m calculating. For instance, in the sum, product, and max functions that follow, the function returns an Int. In the Fibonacci example the function prints its result as it goes along, so it doesn’t return anything.

As another note, in some cases it helps to have an “accumulator” function inside your main function. I show this in the examples that follow, and I’ll describe it more at some point in the future.

Back to top

A recursive ‘sum’ function

The following code shows three ways to calculate the sum of a List[Int] recursively. I don’t think the first approach is practical; it is simple, but results in a StackOverflowError when the list is large.

The second approach shows how to fix the first approach by using a tail-recursive algorithm. This solution uses the “accumulator” I mentioned above.

The third approach shows how to use an if/else construct instead of a match expression. It’s taken from the URL shown.

With that introduction, here’s the code:

package recursion

import scala.annotation.tailrec

/**
 * Different ways to calculate the sum of a list using 
 * recursive Scala methods.
 */
object Sum extends App {

  val list = List.range(1, 100)
  println(sum(list))
  println(sum2(list))
  println(sum3(list))
  println(sumWithReduce(list))
  
  // (1) yields a "java.lang.StackOverflowError" with large lists
  def sum(ints: List[Int]): Int = ints match { 
    case Nil => 0
    case x :: tail => x + sum(tail)
  }

  // (2) tail-recursive solution
  def sum2(ints: List[Int]): Int = {
    @tailrec
    def sumAccumulator(ints: List[Int], accum: Int): Int = {
      ints match {
        case Nil => accum
        case x :: tail => sumAccumulator(tail, accum + x)
      }
    }
    sumAccumulator(ints, 0)
  }
  
  // (3) good descriptions of recursion here:
  // stackoverflow.com/questions/12496959/summing-values-in-a-list
  // this example is from that page:
  def sum3(xs: List[Int]): Int = {
    if (xs.isEmpty) 0
    else xs.head + sum3(xs.tail)
  }
  
}

I don’t want to stray too far from the point of this article, but while I’m talking about “sum” algorithms, another way you can calculate the sum of a List[Int] in Scala is to use the reduceLeft method on the List:

def sumWithReduce(ints: List[Int]) = {
  ints.reduceLeft(_ + _)
}

(That’s all I’ll say about reduceLeft today.)

Back to top

Calculating the “product” of a List[Int] recursively

Calculating the product of a List[Int] is very similar to calculating the sum; you just multiply the values inside the function, and return 1 in the Nil case. Therefore I’ll just show the following code without discussing it:

package recursion

import scala.annotation.tailrec

/**
 * Different ways to calculate the product of a List[Int] recursion.
 */
object Product extends App {

    val list = List(1, 2, 3, 4)
    println(product(List(1, 2, 3, 4)))
    println(product2(List(1, 2, 3, 4)))

    // (1) basic recursion; yields a "java.lang.StackOverflowError" with large lists
    def product(ints: List[Int]): Int = ints match { 
        case Nil => 1
        case x :: tail => x * product(tail)
    }

    // (2) tail-recursive solution
    def product2(ints: List[Int]): Int = {
      @tailrec
      def productAccumulator(ints: List[Int], accum: Int): Int = {
          ints match {
              case Nil => accum
              case x :: tail => productAccumulator(tail, accum * x)
          }
      }
      productAccumulator(ints, 1)
  }

}
Back to top

Calculating the “max” of a List[Int] recursively

Calculating the “max” of a List[Int] recursively is a little different than calculating the sum or product. In this algorithm you need to keep track of the highest value found as you go along, so I jump right into using an accumulator function inside the outer function.

I show two approaches in the source code below, the first using a match expression and the second using an if/else expression:

package main.scala.recursion

import scala.annotation.tailrec

object Max extends App {

  val list = List.range(1, 100000)
  println(max(list))
  println(max2(list))
  
  // 1 - using `match`
  def max(ints: List[Int]): Int = { 
    @tailrec
    def maxAccum(ints: List[Int], theMax: Int): Int = {
      ints match {
        case Nil => theMax
        case x :: tail =>
          val newMax = if (x > theMax) x else theMax
          maxAccum(tail, newMax)
      }
    }
    maxAccum(ints, 0)
  }

  // 2 - using if/else
  def max2(ints: List[Int]): Int = { 
    @tailrec
    def maxAccum2(ints: List[Int], theMax: Int): Int = {
      if (ints.isEmpty) {
        return theMax
      } else {
        val newMax = if (ints.head > theMax) ints.head else theMax
        maxAccum2(ints.tail, newMax)
      }
    }
    maxAccum2(ints, 0)
  }

}
Back to top

A Scala Fibonacci recursion example

The code below shows one way to calculate a Fibonacci sequence recursively using Scala:

package recursion

/**
 * Calculating a Fibonacci sequence recursively using Scala.
 */
object Fibonacci extends App {

    println(fib(1, 2))
  
    def fib(prevPrev: Int, prev: Int) {
        val next = prevPrev + prev
        println(next)
        if (next > 1000000) System.exit(0)
        fib(prev, next)
    }

}

There are other ways to calculate a Fibonacci sequence, but since my function takes two Int values as arguments and prints as it goes along, this solution works.

Back to top

A tail-recursive Fibonacci recursion example

Here’s another example of how to write a Fibonacci method, this time using a tail-recursive algorithm:

import scala.annotation.tailrec

/**
 * The `fibHelper` code comes from this url: rosettacode.org/wiki/Fibonacci_sequence#Scala  
 */
object FibonacciTailRecursive extends App {
    
    println(fib(9))

    def fib(x: Int): BigInt = {
        @tailrec def fibHelper(x: Int, prev: BigInt = 0, next: BigInt = 1): BigInt = x match {
            case 0 => prev
            case 1 => next
            case _ => fibHelper(x - 1, next, (next + prev))
        }
        fibHelper(x)
    }

}

As I’ve learned more about functional programming in Scala, I’ve come to prefer approaches like this. A cool thing about the fib method is that it has another method named fibHelper embedded inside of it. Besides just being cool that you can do even that, it’s nice because it helps limit the scope of the fibHelper method.

Back to top

Recursive factorial algorithms

Finally, without much discussion, the following Scala code shows two different recursive factorial algorithms, with the second solution showing the tail-recursive solution:

package recursion

import scala.annotation.tailrec

object Factorial extends App {

    println(factorial(5))
    println(factorial2(5))

    // 1 - basic recursive factorial method
    def factorial(n: Int): Int = { 
        if (n == 0) 1
        else        n * factorial(n-1)
    }
  
    // 2 - tail-recursive factorial method
    def factorial2(n: Long): Long = {
        @tailrec
        def factorialAccumulator(acc: Long, n: Long): Long = {
            if (n == 0) acc
            else factorialAccumulator(n*acc, n-1)
        }
        factorialAccumulator(1, n)
    }
 
}
Back to top

Summary

I hope these examples of recursive programming techniques in Scala have been helpful. As mentioned, I’ll try to add more when I can, but until then, I hope this collection of recursion examples has been helpful.

Back to top

You can use reduce to sum a list of ints, since the order that you sum them is irrelevant, eg:

ints.reduce(_ + _)

reduce and reduceLeft will throw an exception if the list is empty, since the list has no values to return. One solution to this is to use reduceOption, which will return None if the list is empty. But for sum, there is a logical answer to the sum of an empty list, it's 0, so it would make more sense to use fold, by folding over the value 0, which means an empty list can return 0:

ints.fold(0)(_ + _)

Permalink

Here's a better Fib:

def fib(n: Int): Int = fibAcc(0, 1, 1, n)

/**
* Compute the Fibonacci sequence at a given index knowing two previous values
* @param n the number for which we wish to calculate the Fibonacci sequence
* @param crt the current index in the Fibonacci sequence
* @param fpp value of F(crt-1)
* @param fp value of F(crt)
* @return value of Fibonacci sequence at index n
*/
@tailrec
def fibAcc(fpp: Int, fp: Int, crt: Int, n: Int): Int = {
if (n < 2) n
else
if (crt + 1 == n) fpp + fp
else
fibAcc(fp, fpp + fp, crt + 1, n)
}

Note that we define the sequence as
f(0)=0, f(1)=1, f(2)=1, f(3)=2, ...

Add new comment

The content of this field is kept private and will not be shown publicly.

Anonymous format

  • Allowed HTML tags: <em> <strong> <cite> <code> <ul type> <ol start type> <li> <pre>
  • Lines and paragraphs break automatically.
By submitting this form, you accept the Mollom privacy policy.