Re: Tail recursion to while iteration in 2 easy steps

Discussion in 'Python' started by Terry Reedy, Oct 2, 2013.

  1. Terry Reedy

    Terry Reedy Guest

    On 10/2/2013 8:31 AM, wrote:
    > On Tue, Oct 1, 2013, at 17:30, Terry Reedy wrote:
    >> Part of the reason that Python does not do tail call optimization is
    >> that turning tail recursion into while iteration is almost trivial, once
    >> you know the secret of the two easy steps. Here it is.

    >
    > That should be a reason it _does_ do it - saying people should rewrite
    > their functions with loops means declaring that Python is not really a
    > multi-paradigm programming language but rather rejects functional
    > programming styles in favor of imperative ones.


    It is true that Python does not encourage the particular functional
    style that is encouraged by auto optimization of tail recursion. A
    different functional style would often use reduce (or fold) instead.

    Some other points I left out in a post of medium length yet brief for
    the topic.

    1. If one starts with body recursion, as is typical, one must consider
    commutativity (possibly associativity) of the 'inner' operator in any
    conversion.

    2. Instead of converting to tail recursion, one might convert to while
    iteration directly.

    3. One often 'polishes' the while form in a way that cannot be done
    automatically.

    4. While loops are actually rare in idiomatic Python code. In Python,
    for loops are the standard way to linearly process a collection. The
    final version I gave for a factorial while loop,

    def fact_while(n):
    if n < 0 or n != int(n):
    raise ValueError('fact input {} is not a count'.format(n))
    fac = 1
    while n > 1:
    fac *= n
    n -= 1
    return fac

    should better be written with a for loop:

    def fact_for(n):
    if n < 0 or n != int(n):
    raise ValueError('fact input {} is not a count'.format(n))
    fac = 1:
    for i in range(2, n):
    fac *= n

    When the input to a function is an iterable instead of n, the iterable
    should be part of the for loop source expression. For loops are
    integrated with Python's iterator protocol in much the same way that
    recursion is integrated with list first:rest pattern matching in some
    functional languages. It is true that Python encourages the use of for
    loops and for clauses in comprehensions (a functional construct).

    5. Conversion of apparent recursion to iteration assumes that the
    function really is intended to be recursive. This assumption is the
    basis for replacing the recursive call with assignment and an implied
    internal goto. The programmer can determine that this semantic change is
    correct; the compiler should not assume that. (Because of Python's late
    name-binding semantics, recursive *intent* is better expressed in Python
    with iterative syntax than function call syntax. )

    --
    Terry Jan Reedy
    Terry Reedy, Oct 2, 2013
    #1
    1. Advertising

  2. On Thursday, October 3, 2013 5:33:27 AM UTC+8, Terry Reedy wrote:
    > On 10/2/2013 8:31 AM, wrote:
    >
    > > On Tue, Oct 1, 2013, at 17:30, Terry Reedy wrote:

    >
    > >> Part of the reason that Python does not do tail call optimization is

    >
    > >> that turning tail recursion into while iteration is almost trivial, once

    >
    > >> you know the secret of the two easy steps. Here it is.

    >
    > >

    >
    > > That should be a reason it _does_ do it - saying people should rewrite

    >
    > > their functions with loops means declaring that Python is not really a

    >
    > > multi-paradigm programming language but rather rejects functional

    >
    > > programming styles in favor of imperative ones.

    >
    >
    >
    > It is true that Python does not encourage the particular functional
    >
    > style that is encouraged by auto optimization of tail recursion. A
    >
    > different functional style would often use reduce (or fold) instead.
    >
    >
    >
    > Some other points I left out in a post of medium length yet brief for
    >
    > the topic.
    >
    >
    >
    > 1. If one starts with body recursion, as is typical, one must consider
    >
    > commutativity (possibly associativity) of the 'inner' operator in any
    >
    > conversion.
    >
    >
    >
    > 2. Instead of converting to tail recursion, one might convert to while
    >
    > iteration directly.
    >
    >
    >
    > 3. One often 'polishes' the while form in a way that cannot be done
    >
    > automatically.
    >
    >
    >
    > 4. While loops are actually rare in idiomatic Python code. In Python,
    >
    > for loops are the standard way to linearly process a collection. The
    >
    > final version I gave for a factorial while loop,
    >
    >
    >
    > def fact_while(n):
    >
    > if n < 0 or n != int(n):
    >
    > raise ValueError('fact input {} is not a count'.format(n))
    >
    > fac = 1
    >
    > while n > 1:
    >
    > fac *= n
    >
    > n -= 1
    >
    > return fac
    >
    >
    >
    > should better be written with a for loop:
    >


    As I pointed out before, an accelerated version without the limit
    of the stack depth for computing
    facotrials can be obtained
    by storing a list of products of primes
    first.

    Of course integer divisions are
    required to transform the to stack
    depth problem into the size of the
    32-64 bit heap space.
    88888 Dihedral, Oct 4, 2013
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Terry Michaels

    Tail Call Optimization (Tail Recursion)

    Terry Michaels, Apr 18, 2011, in forum: Ruby
    Replies:
    16
    Views:
    309
    Robert Klemme
    Apr 20, 2011
  2. Terry Reedy
    Replies:
    66
    Views:
    375
    Charles Hixson
    Oct 9, 2013
  3. Replies:
    3
    Views:
    134
    Steven D'Aprano
    Oct 2, 2013
  4. Mark Janssen
    Replies:
    0
    Views:
    126
    Mark Janssen
    Oct 2, 2013
  5. Replies:
    1
    Views:
    96
    Steven D'Aprano
    Oct 4, 2013
Loading...

Share This Page