change the recursive function to tail recursive-CodePudding

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

How to change to a tail recursive function?

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

CodePudding user response：

if you want this with a tail-call you need to add an accumulator:

def singlesR(xs, accumulator=[]):
    if not xs:
        return accumulator

    accumulator = accumulator   [xs[0]]
    return singlesR(xs[1:], accumulator)

note that now the last call before returning is indeed the recursive call to singlesR.

but as stated in the comments: as there is no tail-call optimization in python there will be no performance gain.

note that in your version

return [[xs[0]]]   singlesR(xs[1:])

the call to singlesR is not in tail position - after it is called there is a call to list.__add__.

CodePudding user response：

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.