Factorial - How did you solve it?


#1

One thing that I miss in these exercises is seeing how others might have done the same thing more efficiently, or even just differently. I've enjoyed seeing others solutions on this board.

My first solution was to create a list of the factorials first, then iterate through that list to multiply them all together (this did pass btw):

def factorial(x):
    num_list = []
    while x-1 > 1:
        num_list.append(x)
        x = x-1
    else:
        num_list.append(x)
    total = 1
    for i in num_list:
        total *= i
    return total

This worked, but then I re-read the instructions:

"To calculate the factorial of a non-negative integer x, just multiply all the integers from 1 through x."

That sounded like:

range(1, x)

Or something close to that (actually x+1 because range stop is NOT inclusive). This definitely sounded like it would be simpler. So I re-coded using range and got this:

def factorial(x):
    total = 1
    for i in range(1,x+1):
        total *= i
    return total

Obviously this doesn't play nice with zero or negative integers. So I put in a quick check:

def factorial(x):
    if x <= 0:
        return None
    else:
        total = 1
        for i in range(1,x+1):
            total *= i
        return total

This now returns "None" for any integer below 1. I couldn't figure out a way to just make the algorithm work if it took zero as an input. And since the exercise called for "non-negative integers," that to me includes zero.

How did you solve it?


#2

i did it using factorial
import math
def factorial(x):
total = math.factorial(x)
return total


#3

Hah. Well I hadn't looked at the hint. So factoring 0 as 1 is actually legit:

Note that mathematically, factorial(0) is 1.

However I'm now more confused. How can a function call itself?

Consider having factorial() call itself. When the input is 1, your function could just return 1. Otherwise, it could return the number multiplied by factorial(n - 1).

Where did they introduce the idea of calling the function within the function? How can you call a function that hasn't finished being defined? I'm confused by this "hint" haha.


#4

I don't think that was the intention. :slight_smile:

But the same idea occurred to me when I read the instructions. I figured there was already a defined function for doing that.


#5

Very easily. This is known as recursion and factorial() is a simple example of a recursive function.

def factorial(n):
    if n < 2: return 1
    return n * factorial(n-1)

Python manages what is named a call stack. Each time the second line of the function runs, another return is added to the stack. Once we reach the base case, 1, recursion stops and the Python works back down the call stack, multiplying as it goes.

We may further refactor the above with a Python ternary...

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

Notice that even though we are calling the same function, the value of n is one less than previous. Eventually it reaches 1.

You will no doubt read that in the case of factorial, an iterative function is likely faster and uses fewer resources. See if you can solve this problem with an iterative, rather than the recursive shown above (no fun in having the answer spelled out).


#6

Hi deepstructure
I changed your code a bit. instead of
if x < = 0: return None
, I changed it to if x<=1: return 1

because factorial 0 and 1 = 1

def factorial (x):
    if x <= 1:
        return 1
    else:
        total = 1
        for i in range(1,x+1):
            total *= i
    return total
print factorial (0)
print factorial (1)
print factorial (2)
print factorial (3)
print factorial (4)

#7

Thanks arwaahmed. My first iteration did return 1 for 0 and 1 as inputs:

def factorial(x):
    total = 1
    for i in range(1,x+1):
        total *= i
    return total

I just "fixed" it because I didn't think it should do that. But after reading the hint I realized that original version could work.

However the recursive version is definitely more compact:

def factorial(x):
    return 1 if x < 2 else x * factorial(x - 1)

Still wrapping my head around it, but got lots of nice helpful replies from folks so I get the usage concept now. :slight_smile:


#8

This is the way I did it. I sort of feel like I cheated a little with my variable on the second line (product = 1) but before I started this I didn't know that 0! = 1, and it works with 0 and negative number so I'm happy.

def factorial(x):
    product = 1
    for i in range(1,x+1):
        product = i * product
    return product
print factorial(4)

#9

This is going to make everyone here mad

boom!

def factorial(x):
    if x == 1:
        return 1
    elif x == 2:
        return 2
    elif x == 3:
        return 6
    elif x == 4:
        return 24
    elif x == 5:
        return 120
    elif x == 6:
        return 720
    elif x == 7:
        return 5040
    elif x == 8:
        return 40320
    elif x == 9:
        return 362880
print factorial(x)

was accepted by codecademy
Way to go me!


#10

Here's what I first came up with without using any hit or any other resources. I actually had one other way right before this but didn't save it. It actually does work but CodeCademy is not accepting it as it's saying it took too long and I need to check for infinite loops... But the print statement, last line of code, prints to the console within CodeCademy so I know there is not an infinite loop as that line wouldn't have ran if there was, only loop I have is the while above it.

def factorial(x):
    sum=x*(x-1)
    x-=2
    while(x-1!=0):
        sum+=sum*(x-1)
        x-=1
    return (sum)
sum = factorial(6)
print (sum)

So I'm going to use some ideas from you guys and come up with another one, mine probably doesn't handle negative numbers at all which could be the problem. Just wanted to share the loop thing at least.

Thanks all!


#11

Then I just realized that the above code, probably is hung up on the loop of CodeCademy is using a negative number to test the program. I'm actually going to stick with this and make it work with negatives before I change to something else. Figured I'd not edit and leave up to show the process of problem solving!


#12

Let me start by saying im not an expert by any means so take my feedback at your own discretion. I did do some testing with your code and have 2 points to make.
I used the following resource to test the code and watch it step by step. PythonTutor

1.) I noticed with the code that i cannot enter an x value anywhere to insert a variable into the function. It is always overwritten by the number on line 8 inside of factorial(#)

sum = factorial(6)

Like i said im no expert but I don't think its a good idea to code this way because it makes it hard to modify the variable the function uses without manually going into the code and changing it by hand.

2.) While testing different numbers, again with the PythonTutor tool, i found that any value below 3 creates an infinite loop because line 3 makes the x value a negative or 0. This causes the equation given to keep decreasing the negative and isnt stopped by the "while" loop rules because a negative number is still != 0. in other words the "x" value never reaches zero because it is always decreased by 1 every time it goes through the loop.

I started this problem trying to use a while loop myself and I couldn't figure out how to make it work because the x value just keeps getting modified and I couldn't figure out how to compensate for the change appropriately.

Again im no expert but this is what i found with my testing. In fact I learned alot from playing around with your code, thank you very much!

edit:
Oh, also the problem only tests integers 1-9. If you look at my earlier post here you can see how i was able to exploit this to cause a "success" response from Codecademy.


#13

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.