minte9
LearnRemember



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: 451 days ago