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.
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.
why it works
Consider a few easy examples:
factorial(1)this will immediately return 1
factorial(2)x is 2 in our first scope. x, which is 2 with factorial(x-1).
*x-1 is 1.factorial(1) which is our first case. The result is 1.2This 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.
Let's say you call factorial(3), here's how it would look.
factorial(3):
return 3 * factorial(2) = ?
can't return yet since it doesn't have a value, call factorial(2)
factorial(2):
return 2 * factorial(1) = ?
can't return yet since it doesn't have a value, call factorial(1)
factorial(1):
return 1
now bubbling up, since factorial(1) returns 1
factorial(2) = 2 * 1
returns 2
factorial(3) = 3 * 2
returns 6
end of operation
A general tip for programming is to insert print statements to help you see what's happening as the code runs. This is especially useful when you have broken code that you are trying to fix but is also good for understanding new code. In this case try running the following:
def factorial(x):
print "x", x
if x <= 1:
print "base case, returning 1"
return 1
else:
sub_fact = factorial(x-1)
print "factorial(x-1)", sub_fact
result = x * sub_fact
print "return", result
return result
factorial(4)
Basically stack frame gets created for every call to the factorial(x) and hierarchy of stack frame is formed.Every call waits for the answer from the next call and so on.Finally, when answer is received by the main call it returns the answer.
A stack frame is a part of the call stack, and a new stack frame is created every time a subroutine is called. So, in our recursive Factorial method above, a new stack frame is created every time the method is called. The stack frame is used to store all of the variables for one invocation of a routine. So, remember that a call stack is basically a stack of stack frames.
Yes, factorial of 0 and 1 is 1 and there is no multiplication nor next recursive call.
Else, you have to note that before we multiply with current x, we must get the result out of next factorial.
So, the recursion "enters" itself down to the stop condition (when x==1) and then result rises back, like this:
factorial(5):
(5 *(4 *(3 *(2 *(1*1)))))
- Read it from right to left, which is the order of recursive execution
- Note: (1*1) would not actually be executed because at x==1 recursion stops.
Because of multiplication rule (a*b = b*a) the direction is irrelevant (top to bottom or bottom to top).
