From: Terry Reedy on
On 5/4/2010 1:45 AM, rickhg12hs wrote:
> On May 4, 1:34 am, Cameron Simpson<c...(a)zip.com.au> wrote:
>> On 03May2010 22:02, rickhg12hs<rickhg1...(a)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


From: rickhg12hs on
On May 4, 1:32 pm, Terry Reedy <tjre...(a)udel.edu> wrote:
> On 5/4/2010 1:45 AM, rickhg12hs wrote:
[snip]
> > [To bad there's no tail recursion optimization.]  8-(
>
> That issue is much more complicated than you probably imagine.
[snip]

No imagination is necessary - functional languages (e.g., Erlang) do
it quite well.
From: Terry Reedy on
On 5/4/2010 4:10 PM, rickhg12hs wrote:
> On May 4, 1:32 pm, Terry Reedy<tjre...(a)udel.edu> wrote:
>> On 5/4/2010 1:45 AM, rickhg12hs wrote:
> [snip]
>>> [To bad there's no tail recursion optimization.] 8-(

This is prinarily a space optimization to conserve stack frame space.
The speedup would be minimal. Using while or for loops has the same
space saving with better speedup (slow function are also gone) and
easier optimization in other ways, as I showed.

>> That issue is much more complicated than you probably imagine.
> [snip]
>
> No imagination is necessary - functional languages (e.g., Erlang) do
> it quite well.

More complicated in the Python context. Does Erlang use static or
dynamic name binding, or early versus late local name resolution?
Python, by design, resolves global names within a function each time the
function is called. So whether a call is recursive cannot be determined
until the call is made.

It is not difficult for CPython to space-optimize *all* tail calls,
recursive or not. But this would have the bad effect of leaving gaps in
error tracebacks and is not done for that reason. To only space-optimize
simple recursive tail calls would take more time, and one would still
lose traceback information.

If you imagined all of the above, then indeed I underestimated you ;-).

Terry Jan Reedy


First  |  Prev  | 
Pages: 1 2
Prev: repeat tkinter
Next: Sphinx hosting