Search code examples
pythonrecursiontail-recursion

change the recursive function to tail recursive

def singlesR(xs):
  if xs != [] :
    return  [[xs[0]]] + singlesR(xs[1:])
  else :
      return []

<recursive function>

How to change to a tail recursive function?

#result value
singlesR([1,2,3,4]) == [[1], [2], [3], [4]]
Solution

  • As mentioned in the comment and discussed further in this answer python does not have tail recursion optimization.

    Other languages such as Haskell do support tail recursion. this function could be rewritten in Haskell in as a tail recursive function like this:

    singlesR = singlesR' []
  where singlesR' acc [] = acc
        singlesR' acc (x:xs) = singlesR' ([x]:acc) xs

    The main observation here is that in the tail recursive version all of the work is done inside of the recursive call.