5/15 About the Factorial Hint


#1

I originally solved the problem with this:

def factorial(x):
    result = 1
    if x >= 0 and x == int(x):
        while x > 0:
            result *= x
            x -= 1
        return result
    else:
        return "You have to use a positive integer!"

But I wanted to know if there was a better way to do this (my method seemed not so smart), so I checked out the hint, which suggested letting factorial() call itself. Checked out the forum and learned it was a recursion. Anyhow I eventually ended up with this:

def factorial(x):
    if x >= 2 and x == int(x):  
        return x * factorial(x-1)
    elif x == 1 or x == 0:
        return 1
    else:        
        return "You have to use a positive integer!"

However, this recursion thing seemed rather unintuitive (logically complex for me) and thus not that readable (for me)....

I am curious about which was the better way, and this really bothered me so I lost some time googling to find a way to time the two functions' performance. I didn't understand how to use import timeit and thus kept failing to make it work, but I eventually ended up finding an easy way to do this in IPython (and I had it installed in my computer), and I got this:

"""
Used x = 500 because when using x = 1000 with the recursion solution 
gave me a max recursion depth error...
This just deepend my feeling that recursion wasn't really a great idea...
"""
In [3]: x = 500
In [4]: %timeit factorial_1(x) # the hint's suggested solution
1000 loops, best of 3: 222 µs per loop
In [5]: %timeit factorial_2(x) # my own original solution
10000 loops, best of 3: 115 µs per loop

# Just for the heck of it
In [6]: import math
In [7]: %timeit math.factorial(x)
100000 loops, best of 3: 13.2 µs per loop

I don't know why the loops are different, but anyhow, it looks like my original solution was stupid but still about 2x faster than the recursion solution i.e. recursion is resource expensive and thus not a great idea for this kind of problem (I wonder when it is a good idea to use it...hopefully I'll learn more in the future = =).

Did the hint just suggest using recursion to teach us something new or is this recursion somehow a better solution than what I used initially and why?

If recursion is not a good solution, is there a better way to solve this factorial problem than what I used initially? (Based on what we've learned so far and ignoring import math)

Thanks!


#2

Thank you so much for the info.What I dont understand is :
def factorial(x):
if x >= 2 and x == int(x):
return x * factorial(x-1)
elif x == 1 or x == 0:
return 1
else:
return "You have to use a positive integer!"

in this example in case X is 6. How come the output 720 instead of 30.Because it seems to me we only multiply x with x-1 not all the way down to 1.
Can you please explain?


#3

5! is equal to 5 * 4!
x! is equal to x * (x-1)!

That makes recursion a really elegant solution, in a way we write what the result is, instead of how to compute it.

Recursion is slower because function calls come with a lot of overhead compared to just incrementing a loop and doing a multiplication. There are languages with better support to recursion, in particular functional languages.


#4

I think I need some time to digestive this information.Thank you for the patience !


#5

I think a nice solution to this problem, with no junk, is this:

def factorial(x):
....j=x-1
....while j > 0:
........x *= j
........j -= 1
....return x


#6

Having said that, there is still a lot of junk which I need to get familiar with, when it becomes useful.


#7

Thanks for the explanation!


#8

def factorial(x):
....if x==0:
........return 1
....else:
........return x*factorial(x-1)