recursion - Why is recursive function execution time faster on average with more iterations in python?

Question

I'm comparing the speed of two different functions in python. They are two implementations of some generic algorithm, where one is recursive, and the other uses a stack.

When using time and timeit to view the speed of the one single iteration, the recursive implementation is about 40x slower. This is to be expected as recursion is relatively slow.

However, when I run 1000000 iterations using both time and timeit, the time taken to complete all those iterations for the recursive implementation is only 30% slower than the stack implementation.

This makes no sense to me at all. The reason I used time was to check whether timeit wasn functioning properly when timing the recursive function, because I thought there must have been some error.

It's important to note that I made sure that the same number of iterations were used when timing each function. I also ran these timings multiple times, and I still got the same conclusion.

Are there any potential reasons as to why more iterations on timeit resulted in this recursion algorithm to actually be so close in speed compared to the non-recursive version?

Unfortunately I cannot show the implementation code. I don't need a definitive answer, I just wanted potential ideas as to why this was. However, it was your basic

iterationNum=100000
print(timeit.timeit(recursiveImplementation, number=iterationNum))
print(timeit.timeit(stackImplementation, number=iterationNum))

Answer 1

If you see a large difference between testing 1 iteration and 1000 iterations, it is likely that the recursive function uses some form of memoization held in a global variable that makes subsequent calls faster. Keep in mind that a mutable default parameter could end up with a global scope as well. In any case, there are surely side effects from the recursive implementation that impact subsequent calls