#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Nov  3 16:17:12 2022

@author: leprince
"""


def binomRec(n,k):
    """fonction récursive naïve calculant un coefficient binomial ;
    on doit avoir 0 <= k <= n"""
    if k == 0 or k == n: #inclut le cas n==0
        return 1
    else : 
        return binomRec(n-1,k-1) + binomRec(n-1,k)
    
print(binomRec(3,2))
print(binomRec(10,5))   
print(binomRec(20,10)) #fonctionne encore rapidement   
print(binomRec(25,10)) #long déjà

def binom(n,k):
    """ Calcule le coef binomial de bas en haut
    en remplissant une liste de listes
    """
    tabCoefs = [[0 for j in range(i+1)] for i in range(n+1)]
    for i in range(n+1):
        tabCoefs[i][0] ,  tabCoefs[i][i] =   1 , 1
    for i in range(2,n+1): # remplissage ligne par ligne du tableau
        for j in range(1,min(k+1,i)): # le min gère le cas où k == n
            tabCoefs[i][j] = tabCoefs[i-1][j-1]  + tabCoefs[i-1][j] 
    return tabCoefs[n][k] 

print(binom(3,2))
print(binom(10,5))   
print(binom(20,10)) #  
print(binom(25,10)) #rapide
print(binom(125,100)) #rapide                 
    

def binomRecTab(n,k):
    """fonction récursive   calculant un coefficient binomial 
    avec mémoïzation (dans une liste de listes);
    on doit avoir 0 <= k <= n"""
    tabCoefs = [[0 for j in range(i+1)] for i in range(n+1)]
    def remplissageTab(i,j):
        """ne remplit que les cases nécessaires au calcul du coef bin (i,j), 0<=j<=i"""
        if j == 0 or j == i: #inclut le cas i==0
            tabCoefs[i][j] = 1
        elif tabCoefs[i][j] == 0: #case non encore visitée
            remplissageTab(i-1,j-1)
            remplissageTab(i-1,j)
            tabCoefs[i][j] = tabCoefs[i-1][j-1] + tabCoefs[i-1][j]
    remplissageTab(n,k)
    return tabCoefs[n][k]

print(binomRecTab(3,2))
print(binomRecTab(10,5))   
print(binomRecTab(20,10)) #  
print(binomRecTab(25,10)) #rapide
print(binomRecTab(125,100)) #rapide    


            
def binomRecDict(n,k):
    """fonction récursive   calculant un coefficient binomial 
    avec mémoïzation (dans un dictionnaire) ;
    on doit avoir 0 <= k <= n  """
    dicoBin = {} 
    def remplissageDico(i,j):
        if (i,j) not in dicoBin : 
            if j == 0 or j == i:
                dicoBin[(i,j)] = 1
            else :
                remplissageDico(i-1,j-1)
                remplissageDico(i-1,j)
                dicoBin[(i,j)] = dicoBin[(i-1,j-1)] + dicoBin[(i-1,j)]
    remplissageDico(n,k)
    return dicoBin[(n,k)]



dicoBin = {}
def binomRecDict2(n,k):
    if (n,k) not in dicoBin :
        if k == 0 or k == n:
            dicoBin[(n,k)] = 1
        else :
            dicoBin[(n,k)] = binomRecDict2(n-1,k-1) + binomRecDict2(n-1,k)
    return dicoBin[(n,k)]
        
    
print(binomRecDict2(3,2))
print(binomRecDict2(10,5))   
print(binomRecDict2(20,10)) #  
print(binomRecDict2(25,10)) #rapide
print(binomRecDict2(125,100)) #rapide