tail recursion
Binary Search in Scala (Iterative,Recursion,Tail Recursion Approaches)
Binary Search is a fast & efficient algorithm to search an element in sorted list of elements. It works on the technique of divide and conquer. Data structure: Array Time Complexity: Worst case: O(log n) Average case: O(log n) Best case: O(1) Space complexity: O(1) Let’s see how it can implemented in Scala with different approaches – Iterative Approach – Recursion Approach – Tail Recursion – Driver Program- val arr = Array(1, 2, 4, 5, 6, 7) val target = 7 println(binarySearch_iterative(arr, target) match { case -1 => s"$target doesn't exist in ${arr.mkString("[", ",", "]")}" case index => s"$target exists at index $index" }) println(binarySearch_Recursive(arr, target)() match { case -1 => s"$target doesnt match" case index => s"$target exists a...
Understanding Tail recursion in Scala
Tail recursion is little tricky concept in Scala and takes time to master it completely. Before we get into Tail recursion, lets try to look into recursion. A Recursive function is the function which calls itself. If some action is repetitive, we can call the same piece of code again. Recursion could be applied to problems where you use regular loops to solve it. Factorial program with regular loops – [code lang=”scala”] def factorial(n: Int): Int = { var fact = 1 for(i <- 1 to n) { fact = fact * i; } return fact } [/code] The same can be re-written with recursion like below – [code lang=”scala”] def factorialWithRecursion(n: Int): Int = { if (n == 0) return 1 else return n * factorialWithRecursion(n-1) } [/code] In the recursive approach, we return e...
