## Example 1: Sum of n given number
# using iteration
def iter_sum(n):
total = 0
for i in range(n + 1):
total += i
return total
# using recursion
def recur_sum(n):
# 'n == 0' is the base case here
if n == 0:
return 0
else:
return n + recur_sum(n - 1)
print(iter_sum(5)) # 15
print(recur_sum(5)) # 15
# here iterative solution seems easy/understandable,
# but the recursive solution is much more concise
## Stack calls over recursion
"""
# In our function, recursive calls are made till n is 0,
# so the recursion is bottom-up, and we'll begin from the last line.
# Note: '->' is the output from that call and after '=' is the return value
5) 5 + recur_sum(4) -> 10 = 15 # finally '15' is the result,
which is returned to the original caller
4) 4 + recur_sum(3) -> 6 = 10 # same thing here
3) 3 + recur_sum(2) -> 3 = 6 # similarly the result '3' is returned
here from previous call and added with '3'
2) 2 + recur_sum(1) -> 1 = 3 # the result '1' is returned here from
previous call and added with '2'
1) 1 + recur_sum(0) -> 0 = 1 # this is the last call, as the base case
is hit, now the return calls are made
"""
## Example: Find factorial of n numbers using recursion and memoization
# for storing previous calculation/result we can use a dictionary ('memo' here)
def factorial(input_value, cur_num=2, memo={1: 1}):
# this is the base case, we return 'memo' to the caller
if cur_num > input_value:
return memo
# calculate factorial logic
memo[cur_num] = cur_num * memo[cur_num - 1]
# recursively call the next number, finally return 'memo' from the base case
return factorial(input_value, cur_num + 1, memo)
print(factorial(5)) # {1: 1, 2: 2, 3: 6, 4: 24, 5: 120}
## Stack calls over recursion
"""
# In this function the recursive calls are made till 'cur_num > input_value',
# as soon as it is hit we return to the caller (line 11) and return output 'memo'
# This is a top-down recursive call so we'll begin from top.
# Note: '->' is the output from that call and after '=' is the return value
1) we multiply 2 with 1 which came from memo[1], later store it at memo[2]
memo[2] = 2 * memo[2 - 1] -> 1
2) we multiply 3 with 2 which came from memo[2] and store result at memo[3]
memo[3] = 3 * memo[3 - 1] -> 2
3) similarly we multiply with memo[3] and store at memo[4]
memo[4] = 4 * memo[4 - 1] -> 6
4) lastly we store the final calculation
memo[5] = 5 * memo[5 - 1] -> 24
5) Our base case hits at this call, from there we return
'memo' to the caller (line 11)
# and then return 'memo' from there to the caller from outside of
# the function (line 14).
"""