Call stacks
Exponents
p34 Exponents are calculated by multiplying a number by itself.
""" Calculating exponents: x^n
Iterative, a loop that repeatedly multiplies a number by itself
res = res * x
Recursive, use the power rule:
a^n = a^(n-1) * a^1
Recursive v2, each call cuts the problem in half:
a^6 = a^3 * a^3
a^5 = a^2 * a^2 * a
"""
def pow_interative(x, n):
res = x
for i in range(1, n):
res = res * x
return res
def pow_recursive(x, n):
if n == 0:
return 1 # Base case
res = pow_recursive(x, n-1) * x
return res
def pow_recursive_v2(x, n):
if n == 0:
return 1
res = pow_recursive_v2(x, n // 2) * \
pow_recursive_v2(x, n // 2)
if n % 2 == 0: return res
if n % 2 == 1: return res * x
def native_pow(x, n):
return pow(x, n)
# Tests
assert pow_interative(2, 2) == 4
assert pow_interative(3, 3) == 27
assert pow_recursive(2, 2) == 4
assert pow_recursive(3, 3) == 27
assert pow_recursive(2, 2) == 4
assert pow_recursive(3, 3) == 27
# Time
import time
t1 = time.time(); result = pow_interative(3, 600)
t2 = time.time(); result = pow_recursive(3, 600)
t3 = time.time(); result = pow_recursive_v2(3, 600)
t4 = time.time(); result = native_pow(3, 600)
print("Iterative pow: \t", time.time() - t1, 's')
print("Recursive pow: \t", time.time() - t2, 'sec')
print("Recursive_v2: \t", time.time() - t3, 'sec')
print("Native pow: \t", time.time() - t4, 's')
"""
Iterative pow: 0.0007915496826171875 s
Recursive pow: 0.0007688999176025391 sec
Recursive_v2: 0.0003693103790283203 sec
Native pow: 4.6253204345703125e-05 s
"""
Factorial
Factorials are use in finding permutations number.
""" Factorial 4! = 4x3x2x1
Factorials are use for example in finding permutations number.
Recursive, uses neighbours 5! = 5 * 4!
5 frame objects
Iterrative, multiplies intergers 1 to n in a loop,
1 frame object, better!
"""
def factorial_iterative(n):
p = 1
for i in range(1, n+1):
p = p * i
return p
def factorial_recursive(n):
if n == 1:
return 1
return n * factorial_recursive(n-1)
# Tests
assert factorial_iterative(4) == 24
assert factorial_iterative(5) == 120
assert factorial_recursive(5) == 5 * factorial_recursive(4)
assert factorial_recursive(4) == 4 * factorial_recursive(3)
# Limits
n = factorial_iterative(1001)
print(len(str(n))) # 2571
try:
n = factorial_recursive(1001)
except RecursionError as e:
print(e) # maximum recursion depth exceeded in comparison
Fibonacci
Every number is the sum of previous two numbers.
""" Fibonacci sequence
Every number is the sum of previous two numbers
1 1 2 1 1 2 3 1 1 2 3 5 ...
a b a+b a b a+b a b a+b
Iterrative approach, a loop and two variables (a, b)
The program needs to keep track only of the latest two numbers.
The recursive algorithm is much slower than the iterative one.
It repeats same calculation over and over.
For fibonacci(5) the fibonacci(2) is called four times!
"""
def fibonacci_iterative(n):
a, b = 1, 1
for i in range(1, n-1):
nextb = a + b
a = b
b = nextb
# a, b = b, a + b # oneline
return b
def fibonacci_recursive(n):
if n == 1: return 1
if n == 2: return 1
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)
# Tests
assert fibonacci_iterative(2) == 1
assert fibonacci_iterative(3) == 2
assert fibonacci_iterative(4) == 3
assert fibonacci_iterative(5) == 5
assert fibonacci_recursive(6) == 8
assert fibonacci_recursive(7) == 13
# Time
import time
t1 = time.time(); n1 = fibonacci_iterative(100)
t2 = time.time(); n2 = fibonacci_recursive(36)
print("Iterative: fibonacci(100)", time.time() - t1, 's')
print("Recursive: fibonacci(36) ", time.time() - t2, 's')
"""
Iterative: fibonacci(100) 2.5802948474884033 s
Recursive: fibonacci(36) 2.5803282260894775 s
"""
➥ Questions
