Throw the cat among the pigeons

[Cecil Westerhof]

I am throwing the cat among the pigeons. ;-)

In another thread I mentioned that I liked to have tail recursion in
Python. To be clear not automatic, but asked for.

Looking at the replies I did hit a nerve. But I still want to
continue.

Some things are better expressed recursively for the people reading
the code. But there are two problems with that:
- You can get out of stack space
- It is less efficient

Most of the time the first problem is the most important.

When I write factorial (I know it is already written, but I use it as
an example to show a point), the recursive variant can not be called
with 1.000 without tail recursion. So for functions that could go very
deep, tail recursion would be a blessing.

By the way: I think that even if the recursion does not go further as
500, it is still a good idea to use tail recursion. Why use stack
space when it is not necessary?

But to my surprise tail recursion could even be more efficient. I
wrote two different versions of factorial with self implemented tail
recursion. For bigger values both are more efficient. And I expect
that if the tail recursion is done by the compiler instead of by hand,
it will be a little faster still.

This is the output a run of my code:
    15:05:50: Start with the time needed to calculate 100000 times
    15:05:50: Timing factorial_iterative         (985): 32.265420768002514
    15:06:22: Timing factorial_recursive         (985): 58.381072121992474
    15:07:21: Timing factorial_recursive_old     (985): 64.46238571999129
    15:08:25: Timing factorial_tail_recursion    (985): 40.43312480399618
    15:09:06: Timing factorial_tail_recursion_old(985): 39.70765891499468

    15:09:45: Start with the time needed to calculate 1 times
              No recursive, because without tail recursion you would run out of stack space
    15:09:45: Timing factorial_iterative         (100000): 3.9112528519763146
    15:09:49: Timing factorial_tail_recursion    (100000): 3.928693111985922
    15:09:53: Timing factorial_tail_recursion_old(100000): 4.305187558988109

    15:09:58: Timing factorial_iterative         (200000): 18.081113666004967
    15:10:16: Timing factorial_tail_recursion    (200000): 16.660855480993632
    15:10:32: Timing factorial_tail_recursion_old(200000): 18.169589380006073

    15:10:51: Timing factorial_iterative         (300000): 41.79109025900834
    15:11:32: Timing factorial_tail_recursion    (300000): 38.368264676013496
    15:12:11: Timing factorial_tail_recursion_old(300000): 41.646923307009274

    15:12:52: Timing factorial_iterative         (400000): 78.35287749301642
    15:14:11: Timing factorial_tail_recursion    (400000): 73.17889478098368
    15:15:24: Timing factorial_tail_recursion_old(400000): 89.64840986899799

    15:16:53: Timing factorial_iterative         (500000): 154.76221033901675
    15:19:28: Timing factorial_tail_recursion    (500000): 130.3837693700043
    15:21:39: Timing factorial_tail_recursion_old(500000): 131.41286378499353

    15:23:50: These result show that tail recursion can be interesting
              They show also that the way you use tail recursion is important

As said the most important reason is that code is often more elegant
when written recursively, but you cannot do that if it is possible
that the recursion can go very deep. But if recursively code would be
more elegant and faster, then it would really be interesting to have.

I would not opt for automatically using tail recursion, but only when
the programmer says so. And if it is not possible, that should be an
error.

To make sure it was not a fluke, I ran it again:
    16:01:30: Start with the time needed to calculate 100000 times
    16:01:30: Timing factorial_iterative         (985): 31.465190444985637
    16:02:01: Timing factorial_recursive         (985): 54.562154764978914
    16:02:56: Timing factorial_recursive_old     (985): 55.56128695001826
    16:03:52: Timing factorial_tail_recursion    (985): 36.27355203201296
    16:04:28: Timing factorial_tail_recursion_old(985): 40.36879472099827

    16:05:08: Start with the time needed to calculate 1 times
              No recursive, because without tail recursion you would run out of stack space
    16:05:08: Timing factorial_iterative         (100000): 3.764512833993649
    16:05:12: Timing factorial_tail_recursion    (100000): 3.8083034529990982
    16:05:16: Timing factorial_tail_recursion_old(100000): 4.107901128008962

    16:05:20: Timing factorial_iterative         (200000): 16.076719653996406
    16:05:36: Timing factorial_tail_recursion    (200000): 16.108007609989727
    16:05:52: Timing factorial_tail_recursion_old(200000): 17.71343147099833

    16:06:10: Timing factorial_iterative         (300000): 37.82596729800571
    16:06:48: Timing factorial_tail_recursion    (300000): 40.308226338995155
    16:07:28: Timing factorial_tail_recursion_old(300000): 41.254319412022596

    16:08:09: Timing factorial_iterative         (400000): 77.01277641401975
    16:09:26: Timing factorial_tail_recursion    (400000): 73.4060631209868
    16:10:40: Timing factorial_tail_recursion_old(400000): 80.26402168802451

    16:12:00: Timing factorial_iterative         (500000): 131.84731978402124
    16:14:12: Timing factorial_tail_recursion    (500000): 125.31950747498195
    16:16:17: Timing factorial_tail_recursion_old(500000): 133.39186109701404

    16:18:30: These result show that tail recursion can be interesting
              They show also that the way you use tail recursion is important


-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof