Scala code snippets

tail recursion

package test


object TestSheet {
  println("Welcome to the Scala worksheet")       //> Welcome to the Scala worksheet
  def sum(a:Int,b:Int):Int = {
    def sumF(acc:Int,a:Int,b:Int):Int = {
  		if(a>b) acc
  		else sumF(acc+a,a+1,b)
    }
  	sumF(0,a,b)
  }                                               //> sum: (a: Int, b: Int)Int
  
  def fact(a:Int):Int = {
  	def factF(acc: Int,a: Int): Int = {
  		if(a<0) -1
  		else if(a==0) acc
  		else factF(acc*a,a-1)
  	}
  	factF(1,a)
  	
  }                                               //> fact: (a: Int)Int
  
  
  
  def coinChange(money: Int, coins: List[Int]): Int={
  	def changeF(ways:Int, money: Int, coins: List[Int]):Int = {
  		if(money==0) ways+1
  		else if(money<0) ways
  		else {
  			
  			if(!coins.isEmpty) {
  				val acc= changeF(ways,money-coins.head, coins)
  				changeF(acc, money, coins.tail)
  			}
  			else ways
  		}
  		
  	}
  	changeF(0,money,coins)

  }                                               //> coinChange: (money: Int, coins: List[Int])Int
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  sum(1,3)                                        //> res0: Int = 6
  sum(3,3)                                        //> res1: Int = 3
  sum(0,1)                                        //> res2: Int = 1
  sum(1,99)                                       //> res3: Int = 4950
  sum(2,1)                                        //> res4: Int = 0
  
  fact(0)                                         //> res5: Int = 1
  fact(1)                                         //> res6: Int = 1
  fact(2)                                         //> res7: Int = 2
  fact(3)                                         //> res8: Int = 6
  fact(25)                                        //> res9: Int = 2076180480
  
  
  coinChange(4, List(1,2))                        //> res10: Int = 3
  coinChange(10,List(1,2,3))                      //> res11: Int = 14
  coinChange(0,List(1,2,3))                       //> res12: Int = 1
  coinChange(-1,List(1,2,3))                      //> res13: Int = 0
  coinChange(100,List(1,2,3))                     //> res14: Int = 884
}

Tail recursion Examples in Scala

I am getting introduced to Functional Programming using Scala. One thing that is coming out from my initial learning is that Functional programming demotivates to use loops and mutative (changable) variables. Instead, it relies heavily on recursion especially on Tail Recursion.

Here is some examples of tail recursion functions in Scala

Tail recursion: Why?

1. Using recursion we don't need a mutable state while solving some problem, and this make possible to specify a semantic in simpler terms
2. Pure functional programming means programming without side effects. Which means, if you write a loop for instance, the body of your loop can't produce side effects. Thus, if you want your loop to do something, it has to reuse the result of the previous iteration and produce something for the next iteration. Thus, the body of your loop is a function, taking as parameter the result of previous execution and calling itself for the next iteration with its own result. This does not have a huge advantage over directly writing a recursive function for the loop.
3. A tail recursive function will make all computations first. as its very last action it will make the recursive call. what at this point, is the use of the stack frame? None at all. we don't need our local variables anymore because we're done with all computations. we don't need to know which functions we are in, because we are going to call the very same functions. functional programming languages like Scala can eliminate the creation of new stack frame and just reuse the current stack frame. So there will be no stack overflow!!!