1
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]]
user17732522
  • 53,019
  • 2
  • 56
  • 105
minjun kim
  • 15
  • 6

2 Answers2

0

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__.

hiro protagonist
  • 44,693
  • 14
  • 86
  • 111
  • Thank you very much. I was very nervous when I visited the site for the first time and asked questions. Nevertheless, it helped me a lot by telling me in detail. – minjun kim Mar 21 '22 at 18:00
  • How should I think about the process when I change it to tail recursion? – minjun kim Mar 21 '22 at 18:06
  • no problem! please [accept](https://stackoverflow.com/help/someone-answers) if it is helpful. – hiro protagonist Mar 21 '22 at 18:07
  • how to "think about" recursion? follow the local variables in a debugger. or in [pythontutor](https://pythontutor.com/visualize.html#code=def%20singlesR%28xs,%20accumulator%3D%5B%5D%29%3A%0A%20%20%20%20if%20not%20xs%3A%0A%20%20%20%20%20%20%20%20return%20accumulator%0A%0A%20%20%20%20accumulator%20%3D%20accumulator%20%2B%20%5Bxs%5B0%5D%5D%0A%20%20%20%20return%20singlesR%28xs%5B1%3A%5D,%20accumulator%29%0A%0Aprint%28singlesR%28%5B0,%201,%202,%203%5D%29%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false). – hiro protagonist Mar 21 '22 at 18:11
0

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.

faire
  • 139
  • 6