Recursive functions not returning lists as expected

[Terry Reedy]

On 5/4/2010 4:10 PM, rickhg12hs wrote:
> On May 4, 1:32 pm, Terry Reedy<tjre... at 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