5. Factorial, how does hint solution work?


#1

def factorial(x):
if x == 0:return 1
v = 1
while x > 0 in range(x):
v *= x
x -= 1
return v

This is my code and it works, v is used for storage and x gets counted down.

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

This is the intended solution, but does the function cycle back until it reaches the bottom, and then work its way back up. it seems much slower. Is there any reason why this is better?


#2

What happens when x is less than 1?. Infinite loop.

RuntimeError: maximum recursion depth exceeded

It's important that we consider this when accepting unknown inputs, especially from a user. When the inputs are valid the recursion does work, and explaining it might be more detailed than needs be. We can write the recursion as a return value so we build a return stack and solve the recursion by dumping the stack when a base case is reached.

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

The way a recursion works is by building a stack of return values. Let's say we ask for factorial(5). x is 5 when we start the function. The recursion takes place when x is multiplied by the factorial of 1 less than x. Each return value is stored in a stack. A value times a return value. When the base case is reached, 1 is returned. Then we go back through the stack.

[[[[[1] * 2] * 3] * 4] * 5]
     1! == 1
        2! == 2
             3! == 6
                  4! == 24
                       5! == 120

in reverse order. Each block [] is a return value. Bear in mind that without the base case, we might never get out of a recursive loop, hence the fatal runtime error when it runs out of registers in the stack.


Factorial function? what?
#3

Supplemental:

Python gives us a very nice construct, a ternary statement:

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

These are not always a slam-dunk, but in this instance, it works perfect for our problem. It may be a bit abstract for the OP, but I include it here as another way to view the recursion solution suggested in the hint.


#4

Here's what worked for me:


#6

Here is my code, that worked:


#7

Though I am sure, your code works. I suggest writing the code without using factorial() function in python.
As the exercise is about writing function to find factorial for a number, better to avoid in-built factorial() function.


#8

That would be math.factorial(). It is not a built-in, but an import. For the purpose of this exercise, the function is the one we write, not the math module component. If there were to be a clash, then we would need a different name for our function, such as factoral. Not a problem in this case, though.


#10

hi @mtf,

I have been trying hard to understand this exercise and the thing about max recursion depth, and I think your painstakingly typed explanation has helped to shed some light on this mind-boggling concept :slight_smile:

So I would just like to check one last time with you again:

Essentially for this exercise, it has never been about using a built-in factorial function. I could have done something like:

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

and this will work as well (which I really tried, and it seems to, haha).

If that is the case, I finally understand why that exercise exists :slight_smile:

One last question though: I thought return would cause a function to cease execution, so why is it that it is able to return until it reaches the specified base case, instead of having to stop right after the first return? like if I called anything(10), why would it go on to do 10 * 9 * 8... until x is < 2? why wouldn't the function just compute 10 * 9 and stop there since the return statement is present?

Sorry I am quite the newbie :stuck_out_tongue:


#11

Just so you know, we are not using the built-in, but our own custom function. The built-in has to be imported.

from math import factorial

It returns to the calling method. That's where the return stack comes in. Each return goes up the stack to its caller.


#12

2 posts were split to a new topic: Trying wothout factorial in factorial


#13

How about using an accumulator and create a loop that multiplies the number in range until it reaches n? Mine goes like this:

def factorial(x):

total = 1

if x == 0:
    return (total)

else:
    for num in range(1, (x + 1)):
        total = total * num

    return (total)

#15

Did you miss Post #3, or the discussion as a whole?


#17