Code
def factorial_iter(n):num = 1
while n >= 1:
num = num * n
n = n - 1
return num
def factorial_recur(n):
if n == 1:
# base case that stops recursion
print (' return 1 (this is the top of the stack)')
return 1
else:
print (' return ' + str(n) + '*' + 'factorial_recur(' + str(n-1) + ')')
# the function is calling ITSELF
return n * factorial_recur(n-1)
number = 5
print ('-' * 20)
print ('Using Iteration. Factorial of ' + str(number))
print ('-' * 20)
print (str(factorial_iter(number)))
print (' ' * 20)
print ('-' * 20)
print ('Using Recursion. Factorial of ' + str(number))
print ('-' * 20)
print ("factorial_recur: stack trace")
print ("Note how the function calls itself. This is no different than calling another function")
print ("It is called RECURSION because the function is calling ITSELF")
print ("When it reaches the BASE CASE (n==1), it stops calling itself")
print ("The function MUST stop calling itself at some point, otherwise it will never end (likely run of out memory)")
print ("The innermost function call is evaluated first, where n=1 and then return 2 * 1, then return 3 * 2, and so on")
print ("This is called unwinding of the stack. Start from the BOTTOM and evaluate upwards. Think of a function evaluation as follows.")
print ("(5 * (4 * (3 * 2) * (1)))")
print ("Stack trace")
print (str(factorial_recur(number)))
Output
--------------------Using Iteration. Factorial of 5
--------------------
120
--------------------
Using Recursion. Factorial of 5
--------------------
factorial_recur: stack trace
Note how the function calls itself. This is no different than calling another function
It is called RECURSION because the function is calling ITSELF
When it reaches the BASE CASE (n==1), it stops calling itself
The function MUST stop calling itself at some point, otherwise it will never end (likely run of out memory)
The innermost function call is evaluated first, where n=1 and then return 2 * 1, then return 3 * 2, and so on
This is called unwinding of the stack. Start from the BOTTOM and evaluate upwards. Think of a function evaluation as follows.
(5 * (4 * (3 * 2) * (1)))
Stack trace
return 5*factorial_recur(4)
return 4*factorial_recur(3)
return 3*factorial_recur(2)
return 2*factorial_recur(1)
return 1 (this is the top of the stack)
120
