Tail recursion to while iteration in 2 easy steps

[Steven D'Aprano]

On Wed, 02 Oct 2013 10:04:49 -0400, random832 wrote:

> On Wed, Oct 2, 2013, at 9:32, Steven D'Aprano wrote:
>> Python is not as aggressively functional as (say) Haskell, but it is
>> surely an exaggeration to suggest that the failure to include tail call
>> optimization means that Python "rejects" functional programming styles.
>> You can still write you code in a functional style, it just won't be as
>> heavily optimized.
> 
> IMO, tail call optimization is essential to writing in a functional
> style, since otherwise you end up with a stack overflow error on any
> input above a trivial size.

Hardly essential. Here's some functional code that doesn't rely on tail-
call optimization for efficiency:

result = map(some_function, some_iterator)

In Python 3 that even uses lazy evaluation, for free.

Or you can increase the amount of memory available in the stack. Another 
alternative would be for the compiler to convert your recursive code into 
iterative code. Well, that wouldn't work for Python.

Not all functional code is recursive, and not all recursive functional 
code is tail-recursive. So while Python's lack of tail-call optimization 
is a failure of Best Practice functional *implementation*, it doesn't 
prevent you from writing in a functional *style*.

Ultimately, Python does not pretend to be a pure-functional language. If 
you want Haskell, you know where to get it. Python steals a few good 
ideas from functional programming, like comprehensions and lazy-evaluated 
iterators, provides a few functional programming constructs like map, 
reduce, and filter, and gives you first-class functions as values. You 
can write code in a functional style in Python, but don't mistake that 
for Python being a functional language.

-- 
Steven