minte9
LearnRemember




S R Q

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

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

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    
Recursion, Memoization