Recursion in Scala

How about this:

scala> def inc(n: Int) = n + 1
inc: (n: Int)Int

scala> def dec(n: Int) = n - 1
dec: (n: Int)Int

scala> def add(n: Int, m: Int): Int = m match {
     |   case 0           => n
     |   case _ if m > 0  => add(inc(n), dec(m))
     |   case _           => add(dec(n), inc(m))
     | }
add: (n: Int, m: Int)Int

scala> add(100, 99)
res0: Int = 199

scala> add(100, -99)
res1: Int = 1

Or there is another solution, which is an implementation of the Peano axioms.

scala> def add2(n: Int, m: Int): Int = m match {
     |   case 0           => n
     |   case _ if m > 0  => inc(add2(n, dec(m)))
     |   case _           => dec(add2(n, inc(m)))
     | }
add2: (n: Int, m: Int)Int

Tail Recursion has 3 parts as far as I'm concerning:

• Condition to end recursion
• return value if the condition is met, the returned value is one (or derived from) the parameters of the tail recursive function
• and the call to itself if the condition is unmet.

sample:

def inc(n: Int) = n + 1
def dec(n: Int) = n - 1


def add(n:Int, m:Int, sum: Int):Int = {
  //condition to break/end the recursion
  if (m <= 0) {
    // returned value once condition is met. This is the final output of the recursion
    sum
  } else {
    //call to itself once condition is unmet
    add(inc(n), dec(m), n + m)
  }
}

as you can see, it feels like you are doing while loop but more functional way.

on recursion, calls are stack which result to having it's call stack size as depth of the recursive calls (which can result to stackoverflowexception) on tail recursion it is like how while loop is interpreted.

sample of recursion:

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

Using regular recursion, you could try something like:

  def inc(n: Int) = n + 1
  def dec(n: Int) = n - 1

  def add(n: Int, m: Int): Int = {
    if (m == 0) n
    else add(inc(n), dec(m))
  }

The add function recursively calls itself add, each time incrementing n and reducing m. The recursion stops when m reaches zero, at which point m is returned.