CODEWITHSUNDEEP
scalafunctional-programmingtail-recursion
tommyk
tommyk

Reputation: 3307

two dimensional tail recursion in scala

I am new to Scala and started to learn about tail recursion. I learned that tail recursion in functional programming is a counter part of iterations (for loops) in imperative programming:

Simple C++ loop to sum list elements:

uint32_t sum = 0;
for (size_t i = 0; i < list.length(); ++i) {
    sum += list[i];
}

Scala recursive equivalent:

def listSum(list: List[Int]): Int = {
  def listSumHelper(list: List[Int], sum: Int): Int = {
    if (list.isEmpty) sum
    else listSumHelper(list.tail, sum + list.head)
  }
  listSumHelper(list, 0)
}

Question: What would be a scala recursive equivalent of nested for loops ?

uint32_t sum = 0;
for (size_t i = 0; i < list.width(); ++i) {
    for (size_t j = j < list.height(); ++j) {
        sum += list[i][j];
    }
}

Upvotes: 3

Views: 1394

Answers (2)

Rex Kerr
Rex Kerr

Reputation: 167891

If you want full tail recursion, you should move all your looping into the arguments. So (here without a helper, just for brevity):

def sumsum(xss: List[List[Int]], current: List[Int] = Nil, sum: Int = 0): Int = {
  current match {
    case x :: more => sumsum(xss, more, sum+x)
    case Nil => xss match {
      case xs :: more => sumsum(more, xs, sum)
      case Nil => sum
    }
  }
}

But you probably don't need it unless your loops are really short; just have one tail-recursive function call another each iteration.

Upvotes: 3

axel22
axel22

Reputation: 32335

Simply write an identical list recursion method which works on nested lists (List[List[Int]]):

def listSum2(list: List[List[Int]]): Int = {
  @tailrec def listSumHelper2(list: List[List[Int]], sum: Int): Int = {
    if (list.isEmpty) sum
    else listSumHelper2(list.tail, sum + listSum(list.head))
  }
  listSumHelper2(list, 0)
}

Upvotes: 2

Related Questions