Recursive functions not returning lists as expected

[Terry Reedy]

On 5/4/2010 1:45 AM, rickhg12hs wrote:
> On May 4, 1:34 am, Cameron Simpson<c... at zip.com.au>  wrote:
>> On 03May2010 22:02, rickhg12hs<rickhg1... at gmail.com>  wrote:
>> | Would a kind soul explain something basic to a python noob?
>> |
>> | Why doesn't this function always return a list?
>> |
>> | def recur_trace(x,y):
>> |   print x,y
>> |   if not x:
>> |     return y
>> |   recur_trace(x[1:], y + [x[0]])
>>
>> You need:
>>      return recur_trace(x[1:], y + [x[0]])
>>
>> Otherwise the function returns None.
>
> Ah, an explicit "return" is required.  Thanks!
> [To bad there's no tail recursion optimization.]  8-(

That issue is much more complicated than you probably imagine. Here is 
part of it, using your toy example of computing y +x. [Code snippets 
below are untested and might have typos.]

Write your tail recursive function with the recursive branch first:

def t_r(x,y):
   if x:
     return t_r(x[1:], y+[x[0]])
   else:
     return y

and the conversion ('optimization') to while form is trivial:

def t_w(x,y):
   while x:
     x,y = x[1:], y+[x[0]]
   else:
     return y

Of course, most would omit the 'else:', which I left to emphasize the 
paralellism. More importantly, 'while' loops are relatively rare in 
Python because scanning an iterable (a typical use of tail recursion) 
can be and usually is done (generically) with for loops instead:

def t_f(x,y):
   for o in x:
     y = y + [o]
   return y

Of course, this, like your original code, wastefully creates numerous 
temporary lists (two per iteration) when only one new list is needed for 
the entire process. This is easily fixed in the loop version:

def t_f2(x,y):
   r = y[:]
   for o in x:
     r.append(o)
   return r

Making that important fix in the recursive version is harder since the 
copying should be done exactly once, and not with every recursive call. 
I leave it to you to try either of the two main approaches.

Terry Jan Reedy