Python recursive Factorial Function [duplicate]

Question

Found this solution to make a factorial() function in python, but I am having trouble with understanding 'why' it works.

The function is :

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

I'm having trouble understanding where the actual multiplication happens?

It would seem to me, that the function would keep calling itself until it gets to 1, and returns 1. Can someone enlighten me? I'm sure I'm missing something easy.

Answer 1

Consider a few easy examples:

calling factorial(1)

this will immediately return 1

calling factorial(2)

• x is 2 in our first scope.
• we will enter the else block
• we mulitply x, which is 2 with factorial(x-1). *x-1 is 1.
• We call factorial(1) which is our first case. The result is 1.
• we return 2

This is basically it, for any higher number we get more scopes, always calling factorial with one less, eventually reaching 1 where we terminate and start returning back values.

Answer 2

Where the multiplication happens:

    #        +-------------------------- HERE .MUL A, B  happens
    #        |                                     |  |
    #        |                                     v  v
    #        |                                     x  ( !(x-1) )
    #        v
    return x * factorial(x-1)
#              ---------( -1)
#              |            | <---------------           vvvvvvvvv
#                                             THIS sends recursive call
#                                                  to get B-value "down the line"
#                                                  while A is waiting to
#                                                          to receive B value
#                                                          needed for .MUL A, B
#                                                        B waits for return value
#                                                          from "recusive" call
#                                                          to the same function,
#                                                          but with off by one
#                                                          smaller number
#                                                  UNTIL  A == 2                | more exactly A { 2 | 1 |  0 }
#                                                         B == 1                |              B { 1 | 0 | -1 }
#                                                         for which case        | for which case
#                                                         factorial( 1 ) RETs 1 |   factorial( B ) RETs 1
#                                                         as a terminal state
#                                                         without any .MUL
#                                                         without any deeper
#                                                                     level
#                                                                     recursion
#                                                                     call
#                                                                     thus
#                                                                     "terminal"
#                                                                     state
# and since this moment, all "waiting" .MUL A, B-s start to get processed    
#                                                  from back to front
#                                                  one step after another
#                                                  1 * 2 * 3 * .. * A
#                                                  which is the definition of !A
# Q.E.D.

This is why it works