We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Practice
  2. Functional Programming
  3. Recursion
  4. String Mingling
  5. Discussions

String Mingling

  • serhii_nesteruk + 2 comments

    Hello! I wonder why is this solution is better than mine:

    def recursiveZip(l1: List[Char], l2: List[Char], acc: List[Char]): List[Char] = {
    if(l1.isEmpty) acc
    else recursiveZip(l1.tail, l2.tail, acc ++ List(l1.head, l2.head))
}

    It is tail recursive function, list concatenation has linear complexity

    • PRASHANTB1984 + 0 comments

      many compilers are optimized for tail-recursion which makes such functions less inefficient than one would normally expect them to be. For example, the tailRec keyword in Scala.

    • abhiranjanChallenge Author + 1 comment

      @serhii_nesteruk, :: has constant complexity, while ++ is linear.

      In your code you are applying ++ n times. First on the list of length 1, then 2, then 3, and so on. So overall complexity will be 

      O(1) + O(2) + ... + O(n-1) ~= O(n^2)
      • serhii_nesteruk + 0 comments

        thanks for the explanation!