- ALGORITHMS //
- RECURSION //
- Call Stack
-
Iterative Approach
- Memoization
- Head Tail
Click to Flip Card
Iterative Approach
Which one is preferred, recursion or iteration? How are exponents computed? How are factorial calculated? How can you compute the permutation number? How do you get the fibonacci sequence?
Exponents
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
"""
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
# 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
# Time
import time
t1 = time.time(); result = pow_interative(3, 600)
t2 = time.time(); result = pow_recursive(3, 600)
t4 = time.time(); result = pow(3, 600)
print("Iterative pow: \t", time.time() - t1, 's')
print("Recursive pow: \t", time.time() - t2, 'sec')
print("Native pow: \t", time.time() - t4, 's')
"""
Iterative pow: 0.0007915496826171875 s
Recursive pow: 0.0007688999176025391 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
"""
Logarithm
Use binary search (divide and conquer) to compute logarithm.
import math
def logarithm(x, base):
if x == 1:
return 0
left = 0
right = x
epsilon = 1e-7 # small value (precision of the result)
m = (right + left) // 2 # middle
while right - left > epsilon:
if x <= base**m:
right = m
else:
left = m
m = (left + right) / 2
return round(m, 7)
print(logarithm(8, 2))
print(logarithm(625, 5))
print(logarithm(1000, 10))
assert logarithm(8, 2) == 3 == math.log(8, 2)
assert logarithm(625, 5) == 4 == math.log(625, 5)
assert logarithm(1000, 10) == 3 == round(math.log(1000, 10))
Last update: 303 days ago
