from math import sqrt
import matplotlib.pyplot as plt

## Toutes les fonctions (sauf puissance_0) sont récursives.


def factorielle(n):
    if n == 0:
        return 1
    else:
        return n * factorielle(n - 1)

def somme(L):
    if L == []:
        return 0
    else:
        return L[0] + somme(L[1:])


def somme_bicarree(n):
    if n == 0:
        return 0
    else:
        return n ** 4 + somme_bicarree(n - 1)


def produit(L):
    if L == []:
        return 1
    else:
        return L[0] * produit(L[1:])

def minimum(L):
    if len(L) == 1:
        return L[0]
    else:
        m = minimum(L[1:])
        if m < L[0]:
            return m
        else:
            return L[0]


def puissance_0(x, n):
    p = 1
    for i in range(n):
        p = p * x
    return p

def puissance_1(x, n):
    if n == 0:
        return 1
    else:
        return x * puissance_1(x, n - 1)

def puissance_2(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return puissance_2(x * x, n // 2)
    else:
        return x * puissance_2(x * x, (n - 1) // 2)

# puissance_1(5, 2000) dépasse la profondeur maximale de récursion.
# puissance_2(5, 2000) réussit (O(log n) appels).
# puissance_2 est bien plus rapide que puissance_0 sur de grands exposants.


def Fibonacci(n):
    if n == 0 or n == 1:
        return 1
    else:
        return Fibonacci(n - 1) + Fibonacci(n - 2)

# Fibonacci(35) commence à ralentir ; Fibonacci(40) est déjà très lent (double récursion).
# Fibonacci(100) est infaisable sans mémoïsation : inutile de le lancer.


def binom_1(n, p):
    if p == 0 or p == n:
        return 1
    elif p > n:
        return 0
    else:
        return binom_1(n - 1, p - 1) + binom_1(n - 1, p)

def binom_2(n, p):
    if p == 0:
        return 1
    elif p > n:
        return 0
    else:
        return (n * binom_2(n - 1, p - 1)) // p

# binom_1(100, 2) est acceptable ; binom_1(100, 50) explose.
# binom_2 reste rapide (une seule branche).


def permutations(L):
    if L == []:
        return [[]]
    else:
        resultat = []
        for i in range(len(L)):
            reste = L[:i] + L[i + 1:]
            for p in permutations(reste):
                resultat.append([L[i]] + p)
        return resultat


## Flocon de von Koch

def point_C(A, B):
    x, y = B[0] - A[0], B[1] - A[1]
    return [A[0] + x / 3, A[1] + y / 3]

def point_D(A, B):
    x, y = B[0] - A[0], B[1] - A[1]
    return [A[0] + x / 2 - y * sqrt(3) / 6, A[1] + y / 2 + x * sqrt(3) / 6]

def point_E(A, B):
    x, y = B[0] - A[0], B[1] - A[1]
    return [A[0] + 2 * x / 3, A[1] + 2 * y / 3]

def von_koch(A, B, n):
    if n == 0:
        return [A, B]
    else:
        L = von_koch(A, B, n - 1)
        R = [L[0]]
        for i in range(len(L) - 1):
            P, Q = L[i], L[i + 1]
            R.append(point_C(P, Q))
            R.append(point_D(P, Q))
            R.append(point_E(P, Q))
            R.append(Q)
        return R

# V = von_koch([0, 0], [1, 0], 4)
# plt.figure()
# plt.title("Flocon de von Koch")
# plt.axis("equal")
# plt.plot([p[0] for p in V], [p[1] for p in V])
# plt.show()