Throw the cat among the pigeons

[Dave Angel]

On 05/05/2015 12:18 PM, Cecil Westerhof wrote:

>
> Well, I did not write many tail recursive functions. But what surprised
> me was that for large values the ‘tail recursive’ version was more
> efficient as the iterative version. And that was with myself
> implementing the tail recursion. I expect the code to be more
> efficient when the compiler implements the tail recursion.
>


You've said that repeatedly, so I finally took a look at your webpage
 
https://github.com/CecilWesterhof/PythonLibrary/blob/master/mathDecebal.py

I didn't have your framework to call the code, so I just extracted some 
functions and did some testing.  I do see some differences, where the 
so-called tail_recursive functions are sometimes faster, but I did some 
investigating to try to determine why.


I came up with the conclusion that sometimes the multiply operation 
takes longer than other times.  And in particular, i can see more 
variation between the two following loops than between your two functions.


def factorial_iterative(x, simple=False):
     assert x >= 0
     result = 1
     j=2
     if not simple:
         for i in range(2, x + 1):
             result *= i
             j += 1
     else:
         for i in range(2, x + 1):
             result *= j
             j += 1
             pass

     return result

When the "simple" is True, the function takes noticeably and 
consistently longer.  For example, it might take 116 instead of 109 
seconds.  For the same counts, your code took 111.

I've looked at dis.dis(factorial_iterative), and can see no explicit 
reason for the difference.



-- 
DaveA