Le triangle de Pascal récursif

Le triangle de Pascal récursif.

Les coefficients binomiaux vérifient $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\left(\genfrac{}{}{0ex}{}{n}{n}\right)=1$ et, pour $0<k<n$, la relation de Pascal $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$.

• Écrire une fonction récursive binomial(n, k) pour $0\le k\le n$.
• Justifier que la fonction termine.
• Modifier la fonction pour compter le nombre total d'appels. Que vaut-il pour $\left(\genfrac{}{}{0ex}{}{20}{10}\right)$ ? Expliquer pourquoi ce nombre vaut $2\left(\genfrac{}{}{0ex}{}{n}{k}\right)-1$.