def is_odd(n):
    "Check if n is odd"
    # Check if n is divisible by 2
    if n%2 == 0:
        return False
    else:
        return True

# Test the function for integers from 0 to 10
for i in range(11):
    print('Is', i, 'odd?', is_odd(i))

"""
Explanation: Exercise 04.1 (simple function)
Write a function called is_odd which takes an integer as an argument and returns True if the argument is odd, otherwise returns False. Test your function for several values.
End of explanation
"""


def magnitude(x, y, z=0):
    "Calculate the length of a 2 or 3-dimensional vector"
    return math.sqrt(x**2 + y**2 + z**2)

# Test some cases
print(magnitude(0, 0)) # 0
print(magnitude(1, 1)) # square root of 2
print(magnitude(3, 4)) # 5
print(magnitude(3, 4, 5)) # 7.07106...

"""
Explanation: Exercise 04.2 (functions and default arguments)
Write a single function that takes the components of a vector of length 2 or 3 and returns the magnitude.
Use default arguments to handle vectors of length 2 or 3 with the same code. Test your function for correctness against hand calculations for a selection of values.
End of explanation
"""


def area(x0, y0, x1, y1, x2, y2):
    "Calculate the area of a triangle given the vertices coordinates"
    return abs((x0*(y1-y2) + x1*(y2-y0) + x2*(y0-y1)) / 2)

# Test some cases
print(area(0, 0, 1, 0, 0, 1)) # 0.5
print(area(0, 0, 5, 0, 0, 8)) # 20

"""
Explanation: Exercise 04.3 (functions)
Given the coordinates of the vertices of a triangle, $(x_0, y_0)$, $(x_1, y_1)$ and $(x_2, y_2)$, the area $A$ of a triangle is given by:
$$
A = \left| \frac{x_0(y_1  - y_2) + x_1(y_2 - y_0) + x_2(y_0 - y_1)}{2} \right|
$$
Write a function that computes the area of a triangle given the coordinates of the vertices.
Test the output of your function against some known solutions.
End of explanation
"""


def fact(n):
    "Calculate factorial recursively"
    if n == 0:
        return 1
    else:
        return n*fact(n-1)

# Test the function against the factorial from math module
print('Reference factorial:', math.factorial(5))
print('Calculated factorial:',fact(5))

"""
Explanation: Exercise 04.4 (recursion)
The factorial of a non-negative integer $n$ ($n!$) is expressed recursively by:
$$
n! = 
\begin{cases}
1 & n = 0 \
(n - 1)! \,n & n > 0
\end{cases}
$$
Using recursion, program a function for computing the factorial.
Test your function against the math.factorial function, e.g.
End of explanation
"""


def f(x):
    #return x**3 - 6*x**2 + 4*x + 12
    return x**2 + x - 20 # Roots = -5, 4

"""
Explanation: Exercise 04.5 (functions and passing functions as arguments)
Restructure your program from the bisection exercise in Activity 02 to 

Use a Python function to evaluate the mathematical function $f$ that we want to find the root of; 

and then

Encapsulate the bisection algorithm inside a Python function, which takes as arguments:
the function we want to find the roots of,
the points $x_{0}$ and $x_{1}$ between which we want to search for a root,
the tolerance for exiting the bisection algorithm (exit when $|f(x)| < \text{tol}$)
maximum number of iterations (the algorithm should exit once this limit is reached)



For the first step, use a function for evaluating $f$, e.g.:
def f(x):
    # Put body of the function f(x) here, and return the function value

For the second step, encapsulate the bisection algorithm in a function:
def compute_root(f, x0, x1, tol, max_it):
    # Implement bisection algorithm here, and return when tolerance is satisfied or
    # number of iterations exceeds max_it

    # Return the approximate root, value of f(x) and the number of iterations
    return x, f, num_it

# Compute approximate root of the function f
x, f_x, num_it = compute_root(f, x0=3, x1=6, tol=1.0e-6, max_it=1000)

Try testing your program for a different function. A quadratic function, whose roots you can analytically, would be a good test case.
Function for evaluating $f$.
Note that this method does not work for functions tanget to the $x$ axis, such as $x^2 - 8x + 16 = (x - 4)^2$.
End of explanation
"""


def compute_root(f, x0, x1, tol, max_it):
    """Computes the root of f between x0 and x1 using bisection,
        stops if the value of f at the root is under tol or if max_it is reached
        and returns the root, the value of f at the root and the number of iterations"""
    for i in range(max_it):
    
        # Compute x_mid
        x_mid = (x0 + x1) / 2

        # Compute f for the three values
        f_0, f_1, f_mid = f(x0), f(x1), f(x_mid)

        # Check the value of f_0*f_mid to determine how to update the endpoints
        if f_0*f_mid < 0:
            x1 = x_mid
        else:
            x0 = x_mid
        
        # Check if f is under tol
        if abs(f_mid) < tol:
            return x_mid, f_mid, i+1

    # Return the approximate root in case max_it is reached
    return x_mid, f_mid, i+1

# Test for the function f
x, f_x, num_it = compute_root(f, x0=3, x1=6, tol=1.0e-6, max_it=1000)

print('Approximate root:', x)
print('Value of f:', f_x)
print('Number of iterations:', num_it)

print('-----------------------------------------------------------')

x, f_x, num_it = compute_root(f, x0=-7, x1=0, tol=1.0e-6, max_it=1000)

print('Approximate root:', x)
print('Value of f:', f_x)
print('Number of iterations:', num_it)

"""
Explanation: Bisection algorithm function:
End of explanation
"""


def compute_root_rec(f, x0, x1, tol, max_it):
    """Computes the root of f between x0 and x1 using bisection recursively,
        stops if the value of f at the root is under tol or if max_it is reached
        and returns the root, the value of f at the root and the number of iterations"""
    # Base case 1: value under minimum tollerance
    if abs(f((x1+x0)/2)) < tol:
        return (x1+x0)/2, f((x1+x0)/2), max_it
    
    # Base case 2: maximum number of iterations reached
    elif max_it == 1:
        return (x1+x0)/2, f((x1+x0)/2), max_it
    
    # Check the value of f_0*f_mid to determine how to update the endpoints
    elif f(x0)*f((x1+x0)/2) < 0:
        return compute_root_rec(f, x0, (x1+x0)/2, tol, max_it-1)
    else:
        return compute_root_rec(f, (x1+x0)/2, x1, tol, max_it-1)

# Test for the function f
x, f_x, num_it = compute_root(f, x0=3, x1=6, tol=1.0e-6, max_it=1000)

print('Approximate root:', x)
print('Value of f:', f_x)
print('Number of iterations:', num_it)

print('-----------------------------------------------------------')

x, f_x, num_it = compute_root(f, x0=-7, x1=0, tol=1.0e-6, max_it=1000)

print('Approximate root:', x)
print('Value of f:', f_x)
print('Number of iterations:', num_it)

"""
Explanation: Optional extension
Use recursion to write a compute_root function that does not require a for or while loop.
End of explanation
"""


