minte9
LearnRemember / ALGORITHMS



Exponents / Iteration vs Recursion 

 
""" Exponents are calculated by multiplying a number by itself.
    res = x^n

Iterative approach uses a loop that repeatedly multiplies a number by itself:
    res = res * x

Recursive approach uses the power rule: 
    a^n = a^(n-1) * a^1 

For most of the tasks, an iterative approach, with loops that repeat a task,
is usually better than recursion.
"""

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

assert pow_interative(2, 2) == 4
assert pow_recursive(3, 3) == 27
print("2^2 =", pow_interative(2,2))
print("3^3 =", pow_recursive(3,3))

# 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  3^600: ", time.time() - t1, 's') 
print("Recursive  3^600: ", time.time() - t2, 'sec') 
print("Native pow 3^600: ", time.time() - t4, 's') 

"""
    2^2 = 4
    3^3 = 27
    Iterative  3^600:   0.0007915496826171875 s
    Recursive  3^600:   0.0007688999176025391 sec
    Native pow 3^600:      4.6253204345703125e-05 s
"""

Factorial / Iteration vs Recursion 

 
""" A factorial, denoted by an exclamation point (n!), is the product of 
all positive integers less than or equal to a given non-negative integer n 
4! = 4x3x2x1

Iterrative, multiplies intergers 1 to n in a loop, 
1 frame object (function call)

Recursive, uses neighbours 5! = 5 * 4!
5 frame objects 
"""

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)

assert factorial_iterative(4) == 24
assert factorial_recursive(5) == 5 * factorial_recursive(4)

print("4! =", factorial_iterative(4))
print("5! =", factorial_recursive(5))

# Limits
n = factorial_iterative(30000)
print(f"Iterative factorial 30.000 iterations:", len(str(n)))

# Recursive approach limit (< 3000)
try:    
    n = factorial_recursive(3000)
except RecursionError as e:
    print(f"Recursive factorial 3.000 iterations limit reached!")
    print(f"RecursionError: {e}")

"""
    4! = 24
    5! = 120
    Iterative factorial 30.000 iterations: 121288
    Recursive factorial 3.000 iterations limit reached!
    RecursionError: maximum recursion depth exceeded in comparison
"""

Fibonacci / Iteration vs Recursion

Every number is the sum of previous two numbers. 
 
""" In Fibonacci sequence every number is the sum of previous two numbers.
    0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Iterrative approach, a loop and two variables (a, b)
The program needs to keep track only of the latest two numbers.
    0 1 1     0 1 1 2       0 1 1 2 3     0 1 1 2 3 5       ... 
    a b a+b     a b a+b         a b a+b         a b a+b

The recursive algorithm is much slower than the iterative, it repeats same calculation.
For example, in fibonacci(5) the fibonacci(2) is called four times!
"""

def fibonacci_iterative(n):
    a, b = 0, 1
    for i in range(1, n):
        nextb = a + b
        a = b
        b = nextb
        # a, b = b, a + b # oneline
    return b

def fibonacci_recursive(n):
    if n <= 2: 
        return 1
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

# Tests
assert fibonacci_iterative(1) == 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

#Output
print("The third Fibonnaci number is:", fibonacci_iterative(3))
print("The forth Fibonnaci number is:", fibonacci_iterative(4))
print("The fifth Fibonnaci number is:", fibonacci_iterative(5))

# Time
import time
print("\nThe recursive algorithm is much slower than the iterative.")
print("Processing ...")
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') 

"""
    The third Fibonnaci number is: 2
    The forth Fibonnaci number is: 3
    The fifth Fibonnaci number is: 5

    The recursive algorithm is much slower than the iterative.
    Processing ...
    Iterative: fibonacci(100) 2.685002088546753 s
    Recursive: fibonacci(36)  2.6850242614746094 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))






Questions and answers




Which one represents the multiplication of a number by itself?

  • a) exponent
  • b) factorial

Which one multiply a number by smaller numbers?

  • a) fibonacci
  • b) factorial


References