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

--
https://mail.python.org/mailman/listinfo/python-list

Reply via email to