5. Factorial...I know the answer, just not WHY it's the answer


#1




I saw this code in another thread.
It works, but I don't understand WHY or HOW it works..I'd ask there, but the thread's already closed:

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


Any and all help will be GREATLY appreciated.


Factorial. Another algorithm
Practice Makes Perfect Factorial
Factorial Question
#2

Hi, @colleen412 ,

This is a Python ternary expression ...

x * factorial(x - 1) if x > 0 else 1

The if and else divide the expression into three parts.

The middle part, x > 0, is a condition.

If the condition evaluates to True, then the entire ternary expression evaluates to the result of evaluation of the portion of the expression that is to the left of the if.

If the condition evaluates to False, then the entire ternary expression evaluates to the result of evaluation of the portion of the expression that is to the right of the else.

This part of the expression is interesting, in that the factorial function is calling itself ...

x * factorial(x - 1)

Recursion is a process in which a function calls itself. It might be a good idea to Google that term.

The 1 to the right of the else is a base case that enables the recursion to terminate and have the function return 1 when x is equal to 0.


#3

Hi colleen412,
You can easily understand with this code.
`

`


#5

if it is so simple, can you explain how the recursion in this solution works?


#6

You can get you answer here in this link. Just read it carefully.


#7

if your solution was so simply you should be able to explain it like appylpye did. I know how the solution work, and how the recursion works.


#8

I think i actually understand this, at least partially...thanks, @meetarpit99!

if x>0, do the calculation x*factorial(x-1)...
if it's 0 or less, return 1...
right?

But, how does it know to keep looping?
And, how can a function call itself?

Thanks for providing an easily understandable answer that i don't have to google parts of! :slight_smile:


#9

I think this is a mistake from codeacademy and I will try to pass this by doing it the hard way. But if you try this it lets you pass lol:

import math
def factorial(x):
..... return math.factorial(x):


#10

there is even a median function you can import (don't do this please), but yes, you can built in function if you want.

But you are here to learn, so is that really what you want?


#11

I know buddy, and if you read what i wrote, I said I am going to do the hard way anyway (to learn), I just pointed out what i found.


#12

I have searched online but so far not found an explanation in a manner I understand fully. Below is how I imagine the recursion works which makes sense to me in my own mind :

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

Says x =3
factorial(3) results in : 3 * factorial(2)
factorial(2) results in : 2 * factorial(1)
factorial(1) results in : 1 * factorial(0)
factorial(0) results in : 1 (now the else 1 is satisfied)

All the above factorial(3), factorial(2), factorial(1) & factorial(0) are stored in a stack (FIFO) internally memory. When factorial(0) evaluated to 1 -> factorial(1) evaluated to 1*1 = 1 -> factorial(2) evaluated to 2*1 =2 -> factorial(3) evaluated to 3*2=6

Could you comment if I am on the right path of thinking on how recursion works ?


#13

Hi @atan4583yahoo.com ,

Yes, you are correct regarding the factorial function recursion, except for a part of this detail ...

It is true that the recursive calls are stored as a stack. However, a stack is LIFO (last-in-first-out) rather than FIFO (first-in-first-out). The FIFO pattern applies to a queue, rather than to a stack.


#14

Could someone explain to me why this with a starting call of factorial(3) wont be: 3*2*1*0*1? The if x>0 doesnt start before you've already done the line : return 1 * factorial(1 - 1)...


#15

if we first remove the ternary expression:

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

we have a bit more overview.

As already mentioned in this post, this is the order:

factorial(3) results in : 3 * factorial(2)
factorial(2) results in : 2 * factorial(1)
factorial(1) results in : 1 * factorial(0)
factorial(0) results in : 1 (now the else 1 is satisfied)

factorial(0) will return 1 (not zero) because the base case is satisfied.


#16

Thank you, I think I get it :slight_smile:


#17

the ternary got me confused for a second (well, i understood it, but wrongly translated it when trying to remove the ternary operator) , the base case should be:

if x == 0:

now factorial(0) would be:

if 0 == 0:

which returns one, and then the function start working backwards through all open returns.

You can also read some more here, this topic has some good answers


#18

Oops, only just realized I wrote FIFO instead of LIFO. Thanks for the correction and help understanding recursion concept, appylpye ! Much appreciated.


#19