def fact(n):
    if n ==  0:
        return 1
    else:
        return n * fact(n-1)
    
print(fact(3))

"""
Explanation: Common functions in algorithms
The Constant Function
$f(n) = c$
Note that any other constant function, $f(n) = c$, can be written as a constant
c times g(n). That is, $f(n) = cg(n)$ in this case.
The Logarithmic Function
f(n) = logb n, for some constant b &gt; 1.

The function is defined as follows:
$x = log_bn$ if and only if $b^x = n$
The Big-Oh" Notation
We say that $f(n)$ is $O(g(n))$ if there is a real contant $c > 0$ and an integer constant $n_0 >= 1$ such that:
$$f(n) <= cg(n), \quad for \quad n >= n_0$$
Recursion
Factorial
End of explanation
"""


def BinarySearch(myList, val, low, high):
    mid = (low + high)//2   #this tripped me up. Can we low + (high-low)//2?
    
    if low > high:
        return False
    if myList[mid] == val:
        return True
    elif val < myList[mid]:
        return BinarySearch(myList, val, low, mid-1)
    else:
        return BinarySearch(myList, val, mid+1, high)

myList = [1,2,3, 10, 20, 35]
BinarySearch(myList, 35, 0, len(myList)-1)

"""
Explanation: BinarySearch
End of explanation
"""


def reverse(S, start, stop):
    if start < stop - 1:
        S[start],S[stop-1] = S[stop-1],S[start] 
        reverse(S, start+1, stop-1)
        
s = [1,2,3,4,5]
reverse(s,0,len(s))
print(s)

"""
Explanation: Recursively reversing a Sequence (or a subset of it)
End of explanation
"""


import math
def ireverse(S, start, stop):
    swaps = math.ceil((stop - start)/2)
    
    for x in range(swaps):
        swap(s, start+x, stop-x)

def swap(s, index1, index2):
    temp = s[index1]
    s[index1] = s[index2]
    s[index2] = temp

s=[1,2,3,4,5,6]
ireverse(s,0,len(s)-1)
print(s)
ireverse(s,2,5)
print(s)

"""
Explanation: How about iteratively?
End of explanation
"""


