5. Factorial solutions


#1

I managed to solve it with the following code:

def factorial(x):
    fact = 1
    for n in range(x):
        n += 1
        fact *= n
    print fact
    return fact

factorial(4)

Now, I could move on. But I feel like this is not the optimal solution and also I'm curious as to what they mean in the hint:

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).

Note that mathematically, factorial(0) is 1.

Do they mean I should call factorial() within the factorial function? Does anybody understand the hint?


#2

The hint reverse to solving factorial using recursion.


#3

hmmm... how do you mean?


#4

recursion is one of the possible ways to solve this problem.

recursion is calling a function inside a function. If you want you can attempt this, by reading about recursion and base case, but i don't think it will add much value at the moment


#5

This would be a recursive solution, I believe:

def factorial(x):
    if x > 0:
        for n in range(x):
            p = x * factorial(n)
        return p
    else:
        return 1

If x is greater than 0, it returns p, which is x times the factorial of the highest value of n, i.e. x - 1 (specified via range).

Hope that helps :slight_smile:


#6

Cool! Okay, so I go through this in my head:

eg. range(4), We've got iteration of 0, 1, 2, 3.

first iteration, 0:
p = 4 * factorial(0) -> This seem slike it's obviously = 0

but when printed out, it equals 1.

For all the iterations, I get in the console:
1
1
2
6
24

I've tried going through the iterations in my head, but i get stuck at

p = x * factorial(n) -> What happens at factorial(n)?

I understand that factorial(n) re-initiates a recursive loop, but wouldn't that loop go on indefinitely? Would be very grateful for an explanation, as I didn't really understand this:

which is x times the factorial of the highest value of n, i.e. x - 1 (specified via range).


#7

(1) During each iteration of the for loop, p resets to x * factorial(n). So, for instance, for range(4) you get:

n = 0 -> p = 4 * factorial(0) = 4
n = 1 -> p = 4 * factorial(1) = 4
n = 2 -> p = 4 * factorial(2) = 8
n = 3 -> p = 4 * factorial(3) = 24

Since the range is 4, the loop will stop here and return the current value of p, which is 4 * factorial(3), i.e. 24. (The p-values for the other n-values (0 to 2) are irrelevant, we overwrite them with every further iteration of the loop.)

(2)

I understand that factorial(n) re-initiates a recursive loop, but wouldn't that loop go on indefinitely?

Our loop does not go on indefinitely, because it is limited by range. During each iteration of n, the function calls itself, but with a lower value as x. At some point, x is 0 and the function returns 1 without going into another loop.

(3) Finally:

p = 4 * factorial(0) -> This seem slike it's obviously = 0

but when printed out, it equals 1.

Here, p is not 0 but 4, because factorial(x) returns 1 if x = 0, which is specified by if ... else:

if x > 0:
        ...
    else:
        return 1

Hope that explains it, recursions are a bit tricky to get your head around in the beginning :wink:


#8

else you can try this

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

#9

hi gays. i can''t understand one things.
First of all I read your example and explanation but i still have problems with it.
I use your program and
if factorial(3) i get
1
1
2
6
why i get twice a 1 ??

and if factorial(4) i get
1
1
2
1
1
2
6
24
this things i totally don't understand why i get
1
1
2
1
1
2 ??? i just broke my head with it.
in my mind if factorial(3) i should get
1
2
6
and if factorial(4) i should get
1
2
6
24
i use only your program, nothing change except "print p"
Please could you explain.


#10

f

I assume your code looks like this:
def factorial(x):
if x > 0:
for n in range(x):
p = x * factorial(n)
print p
return p
else:
return 1

factorial(3)

another thing i would like to point out is in : for n in range(x) - n starts from 0 to 2(not 3)

lets get to the main code:
for n in range(x): p = x * factorial(n)
-- now when you go into the for loop your first value is 0, so when program encounters factorial(0) in the p = 3 * factorial(0) it runs the function for factorial of 0 which is 1(which eventually gets printed out in console) because of recursion(calling a function within the function)

now the next value in the loop for n in range(x) is 1
so p = 3 * factorial(1). Now if you find the factorial of 1 is 1 which gets printed out next(remember its a function within a function, so the factorial(1) is called again which prints out 1)

now the next value in the loop for n in range(x) is 2
so p = 3 * factorial(2). Now calling factorial of 2 is 2 which gets printed out next (remember its a function within a function, so the factorial(2) is called again which prints out 2)

At this point our for loop is at the end and we just need to multiply 3 by factorial(2) which becomes 6 and this gets printed out last.

if you try to understand factorial(4) in the same way you would find out at factorial(2) when n = 2 (range for that would be 0 to 3) it goes in the function again and prints out the values for factorial(0) and factorial(1) hence you see corresponding values in the console.

Hope this helps.


#11

oh gay. it was absolutely awesome explanation. thanks a lot.
How i understand
factorial(0) i don't printed
1 - this print then return factorial(1)

  • this print then return factorial(2) and printed factorial(1), then returned it inside function
    1
    2
    • this print then return factorial(3) and the same steps like factorial(1), factorial(2) then returned it inside function
      1
      1
      2
      6

  • this print then return factorial(4) and the same steps like in factorial(1),factorial(2),factorial(3) then returned it inside function
    1
    1
    2
    1
    1
    2
    6
    24


#12

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