Python recursion timings in return statement

Question

I am currently trying to time recursions of factorials and I cannot find a way around printing every factorial in each recursion step. Now I have tried printing it just in the return statement which would solve my problem, but that just ended up in a mess of wall of text with timings being fragmented.

EDIT: I should mention that I am trying to get the cumulative timings of the whole process and not fragmented results like I have below with the print statement.

I tried something like:

return (str(n) + '! = ' + (str(FactResult)) +  
                   ' - Runtime = %.9f seconds' % (end-start))

But here is what I have below as of now.

import time
def factorial(n):
"""Factorial function that uses recursion and returns factorial of
number given."""
start = time.clock()
if n < 1:
    return 1
else:
    FactResult = n * factorial(n - 1)
    end = time.clock()
    print(str(n) + '! - Runtime = %.9f seconds' % (end-start))
    return FactResult

It looks like the indentation is messed up. You obviously can't use the first return since that's a string, unless you want to parse the value out of it every time. — NullUserException
– NullUserException, Commented Oct 10, 2012 at 21:50
Just as a note: recursion is not the fastest implementation of this. — cwallenpoole
– cwallenpoole, Commented Oct 10, 2012 at 21:51
What is not clear to me though is what times are you trying to print? How long it takes for each step to complete? Or do you want a cumulative time? — NullUserException
– NullUserException, Commented Oct 10, 2012 at 21:53
Then why not just do something like start = time.clock(); factorial(n); print time.clock() - start? Also, see timeit — NullUserException
– NullUserException, Commented Oct 10, 2012 at 22:08

pepr · Accepted Answer · 2012-10-11 08:51:30Z

It seems to work fine after fixing the indentation and minor (cosmetic) changes:

import time

def factorial(n):
    """Factorial function that uses recursion and returns factorial of number given."""

    start = time.clock()
    if n < 1:
        return 1
    else:
        FactResult = n * factorial(n - 1)
        end = time.clock()
        print(str(n) + '! =', FactResult, '- Runtime = %.9f seconds' % (end-start))
        return FactResult

factorial(10)

It prints for me... without printing the result value:

c:\tmp\___python\BobDunakey\so12828669>py a.py
1! - Runtime = 0.000001440 seconds
2! - Runtime = 0.000288474 seconds
3! - Runtime = 0.000484790 seconds
4! - Runtime = 0.000690225 seconds
5! - Runtime = 0.000895181 seconds
6! - Runtime = 0.001097736 seconds
7! - Runtime = 0.001294052 seconds
8! - Runtime = 0.001487008 seconds
9! - Runtime = 0.001683804 seconds
10! - Runtime = 0.001884920 seconds

... and with printing the value:

c:\tmp\___python\BobDunakey\so12828669>py a.py
1! = 1 - Runtime = 0.000001440 seconds
2! = 2 - Runtime = 0.001313252 seconds
3! = 6 - Runtime = 0.002450827 seconds
4! = 24 - Runtime = 0.003409847 seconds
5! = 120 - Runtime = 0.004300708 seconds
6! = 720 - Runtime = 0.005694598 seconds
7! = 5040 - Runtime = 0.006678577 seconds
8! = 40320 - Runtime = 0.007579038 seconds
9! = 362880 - Runtime = 0.008463659 seconds
10! = 3628800 - Runtime = 0.009994826 seconds

EDIT

For the cumulative timing, you have to measure outside the call. Otherwise you are not able to capture the start time. It is also more natural:

import time

def factorial(n):
    """Factorial function that uses recursion and returns factorial of number given."""

    if n < 1:
        return 1
    else:
        return n * factorial(n - 1)


n = 10

start = time.clock()
result = factorial(n)
end = time.clock()

print(str(n) + '! =', result, '- Runtime = %.9f seconds' % (end-start))

It prints:

c:\tmp\___python\BobDunakey\so12828669>py a.py
10! = 3628800 - Runtime = 0.000007200 seconds

+1 Always divide I/O from the logic of your programs. Messing them up makes the code harder to reuse, to maintain and it is slower, and that it can be a lot slower(see the results in this answer from 0.0099 to 0.0000072 for 10!...).

Iliyan Bobev · Accepted Answer · 2012-10-10 23:37:02Z

0

Move the "end = time.clock()" and the print statement right before the "return 1" in the block that catches n<1. This is the last execution at the biggest depth of the recursion stack, so all you will miss is the backing up out of it. To get the most proper result, you should follow the suggestion of NullUserException and time outside the recursion method.

answered Oct 10, 2012 at 23:37

Iliyan Bobev

3,1202 gold badges22 silver badges24 bronze badges

Collectives™ on Stack Overflow

Python recursion timings in return statement

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related