Path: csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Terry Reedy <tjreedy@udel.edu>
Subject: Tail recursion to while iteration in 2 easy steps
Date: Tue, 01 Oct 2013 17:30:41 -0400
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.0
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.571.1380663065.18130.python-list@python.org>
Lines: 89
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:55239

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.

Assume that you have already done the work of turning a body recursive 
('not tail recursive') form like

def fact(n): return 1 if n <= 1 else n * fact(n-1)

into a tail recursion like

def fact(n, _fac=1):
   '''Return factorial for any count n.

   Users are not expected to override private parameter _fac.
   '''
   if n <= 1:
     return _fac
   else:  # optional
     return fact(n-1, n * _fac)

(This conversion nearly requires adding an accumulator parameter, as 
done here.

Turn this into while iteration with two easy steps.

1. If not already done, make if-else a statement, rather than an 
expression, with the recursive call in the if branch. If nothing else, 
just use 'not condition' to invert the condition.

def fact(n, _fac=1):
   if n > 1:  # not n <= 1
     return fact(n-1, n * _fac)
   else:  # optional
     return _fac

While contrary to what is often published, this order makes logical 
sense. The recursive call means 'go to the top of this function with new 
bindings for the parameters'. So put it closest to the top. The base 
case means 'we are done, time to leave'. So put it at the bottom.

2. This order also makes the follow substeps work:
2a. Replace 'if' with 'while'.
2b. Replace the recursive call with multiple assignment, using the 
parameters as targets and the arguments as source.
For our example:

def fact(n, _fac=1):
   while n > 1:
     n, _fac = n-1, n * _fac
   else:
     return _fac

The proof of correctness for this conversion might argue that the 
recursive form is equivalent to the following pseudo-Python:

def fact(n, _fac=1):
   label top
   if n > 1:
     n, _fac = n-1, n * _fac
     goto top
   else:
     return _fac

and that this is equivalent to the real Python with while.

At this point, you call pull the initialization of the private parameter 
into the body, remove the else, and even add a value check.

def fact(n):
   if n < 0 or n != int(n):
     raise ValueError('fact input {} is not a count'.format(n))
   fac = 1
   while n > 1:
     n, fac = n-1, n * fac
   return fac

With care, the multiple-assignment statement can usually be turned into 
multiple assignment statements for greater efficiency.

   fac *= n
   n -= 1

But note that the reverse order would be a bug. So I would not do this, 
especially in more complicated situations, without having tests first.

-- 
Terry Jan Reedy