01_Recursivité/Recursivite.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <center> RECURSIVITE </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src='inception.jpg' style='float:right;' width='400' alt=\"photo_abyme\">\n",
    "\n",
    "* Dans cette feuille est abordé le concept de récursivité.\n",
    "* Une fonction récursive est une fonction qui fait appel à elle même dans sa définition.\n",
    "* On peut rapprocher le concept de récursivité à celui de récurrence en mathématiques.\n",
    "* Ce style de programmation permet de résoudre certains problèmes qu'il n'est parfois pas facile de traiter en programmant uniquement avec des boucles.\n",
    "\n",
    "Ci-contre : Une image tirée du film \"Inception\"(Christopher Nolan, 2010)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Une autre façon de voir les choses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Exercice 1 :\n",
    "Pour définir la somme des $n$ premiers entiers, on à l'habitude d'écrire la formule suivante : $0+1+2+...+n$. A l'aide d'une boucle `for`, compléter la fonction `somme(n)` ci-dessous."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def somme(n):\n",
    "    '''Renvoie la somme des n premiers entiers\n",
    "    parametre : n entier naturel\n",
    "    return : la somme des n premiers entiers\n",
    "    '''\n",
    "    S=0\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    return S\n",
    "\n",
    "assert(somme(3)==6)\n",
    "assert(somme(5)==15)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Remarque :\n",
    "* Cette fonction fait bien ce que l'on attend d'elle. Mais on peut remarquer que ce code n'est pas directement lié à la définition. Il n'y a rien qui laisse supposer qu'une variable intermédiaire `S` est nécéssaire pour calculer cette somme.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Définition récursive \n",
    "* Il existe une autre façon de faire : pour calculer la somme des $n$ premiers entiers, il suffit d'ajouter $n$ à la somme des $n-1$ premiers entiers !\n",
    "* Il s'agit d'une définition mathématique que l'on peut rapprocher de la notion de récurrence pour les suites.\n",
    "* La fonction somme peut être définie ainsi :\n",
    "\n",
    "<center> $somme(n)=\\left\\{ \\begin{array}{ll} 0 \\;si \\; n=0\\\\\n",
    "n+somme(n-1) \\;si\\; n>0 \\end{array} \\right.$ </center>\n",
    "\n",
    "Exemples :\n",
    "* $somme(0)=0$\n",
    "* $somme(1)=1+somme(0)=1+0=1$\n",
    "* $somme(2)=2+somme(1)=2+1=3$\n",
    "* $somme(3)=3+somme(2)=3+3=6$\n",
    "\n",
    "#### Remarques :\n",
    "* La définition de $somme(n)$ dépend donc de $somme(n-1)$.\n",
    "* La fonction somme fait appel à elle-même dans sa définition.Il s'agit d'une définition récursive.\n",
    "* Ainsi , pour connaître $somme(n)$, il faut connaître $somme(n-1)$, donc $somme(n-2)$ et ce jusqu'à $somme(0)$ qui vaut $0$.\n",
    "* On obtient $somme(n)$ en ajoutant toutes ces valeurs.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Programmation récursive\n",
    "L'intérêt de cette définition récursive de la fonction somme est qu'elle est calculable, c'est à dire éxécutable par un ordinateur.\n",
    "\n",
    "En particulier, voici le code python de cette définition :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def somme(n):\n",
    "    if n==0:\n",
    "        return 0\n",
    "    else:\n",
    "        return n + somme(n-1)\n",
    "    \n",
    "assert(somme(3)==6)\n",
    "assert(somme(0)==0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src='somme_n.png' style='float:right;' width='300'>\n",
    "\n",
    "#### Remarque : Comment se passe l'éxécution de ce programme ?\n",
    "\n",
    "* Si `n`vaut `0`, alors la valeur `0` est renvoyée, sinon on renvoie `n + somme(n-1)`.\n",
    "\n",
    "\n",
    "* Cet appel qui fait référence à la fonction que l'on est en train de définir est un appel récursif.\n",
    "\n",
    "\n",
    "* Voici ci-contre une façon de représenter ce qui se passe lorsque `somme(3)` est appelé.\n",
    "\n",
    "\n",
    "* On appelle cette représentation un arbre d'appels.\n",
    "\n",
    "\n",
    "* Pour calculer la valeur renvoyée par `somme(3)`, il faut appeler `somme(2)` qui va appeler `somme(1)` qui va appeler `somme(0)` qui va renvoyer `0`.\n",
    "\n",
    "\n",
    "* Le calcul se fait donc à rebours : le calcul de `somme(0)=0` permet celui de `somme(1)=1+0` puis celui de `somme(2)=2+1` et enfin celui de `somme(3)=3+3`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Exercice 2 : \n",
    "En mathématiques, la factorielle d'un entier naturel $n$ est le produit des nombres entiers strictement positifs inférieurs ou égaux à $n$, on la note $n!$ .\n",
    "\n",
    "Par exemples, $4!=24$ et $5!=120$.\n",
    "\n",
    "Compléter la fonction ci-dessous en utilisant la récursivité."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def factor(n):\n",
    "    '''parametre : n entier naturel non nul\n",
    "    return : la factorielle de n'''\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "\n",
    "assert(factor(4)==24)\n",
    "assert(factor(5)==120)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A retenir\n",
    "Une formulation récursive d'une fonction est constituée de plusieurs cas:\n",
    "* Le ou les cas de base : Ce sont ceux pour lesquels on peut obtenir le résultat sans faire appel à la fonction définie elle-même. Dans l'exemple de la fonction `somme(n)`, le cas de base est `n=0`.Les cas de base sont habituellement les cas de valeurs particulières faciles à obtenir.\n",
    "* Le ou les cas récursifs : Ce sont ceux qui renvoient à la fonction en train d'être définie. Pour la fonction `somme(n)`, le cas récursif est `n > 0` .\n",
    "* Pour écrire une fonction récursive, on peut commencer par identifier les cas de base.\n",
    "* Il faut faire confiance à la récursion : on ne doit pas chercher à comprendre ce qui va se passer exactement lors des appels et supposer qu'ils vont donner de bons résultats pour les valeurs sur lesquelles ils opèrent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Exercice 3 :\n",
    "1. Compléter la défintion récursive ci-dessous de la fonction $puissance(x,n)$ qui calcule la valeur de la puissance nième d'un réel $x$:  $x^n=\\underbrace{{x} \\times {x} \\times {...} \\times {x}}_{n \\; fois}$\n",
    "<center> $puissance(x,n)=\\left\\{ \\begin{array}{ll} ? \\;si \\; n=0\\\\\n",
    "? \\;si\\; n>0 \\end{array} \\right.$ </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Compléter ci-dessous la fonction `puissance(x,n)` à l'aide de la définition précédente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def puissance(x,n):\n",
    "    '''Calcule la puissance nième de x\n",
    "    paramètres : \n",
    "    x de type int ou float\n",
    "    n entier naturel\n",
    "    \n",
    "    return :\n",
    "    la puissance nième de x, de type int ou float\n",
    "    '''\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "assert(puissance(2,0)==1)\n",
    "assert(puissance(3,3)==27)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Des formulations plus riches\n",
    "Toute formulation récursive comporte au moins un cas de base et un cas récursif. Mais une grande variété de formes est possible."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cas de base multiples\n",
    "Il peut y avoir plusieurs cas de base identifiables. Par exemple la définition de la fonction puissance peut se faire ainsi :\n",
    "\n",
    "\n",
    "\n",
    "<center> $puissance(x,n)=\\left\\{ \\begin{array}{lll} 1 \\;si \\; n=0\\\\\n",
    "x \\;si \\; n=1\\\\\n",
    "x \\times puissance(x,n-1) \\;si\\; n>1 \\end{array} \\right.$ </center>\n",
    "\n",
    "Ce deuxième cas de base permet d'éviter de faire la multiplication inutile de $x \\times 1$ de la précédente définition.On pourrait bien sûr continuer à ajouter des cas de base pour $n=2$, $n=3$, mais cela ne réduit pas le nombre de multiplication à faire."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Exercice 4 : \n",
    "Modifier la fonction `puissance(n,x)` ci-dessous en insérant le cas de base $n=1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def puissance(x,n):\n",
    "    '''Calcule la puissance nième de x\n",
    "    paramètres : \n",
    "    x de type int ou float\n",
    "    n entier naturel\n",
    "    \n",
    "    return :\n",
    "    la puissance nième de x, de type int ou float\n",
    "    '''\n",
    "    if n==0:\n",
    "        return 1\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    else :\n",
    "        return x*puissance(x,n-1)\n",
    "    \n",
    "assert(puissance(2,0)==1)\n",
    "assert(puissance(4,1)==4)\n",
    "assert(puissance(3,3)==27)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cas récursifs multiples\n",
    "Il est également possible de définir une fonction avec plusieurs cas récursifs.\n",
    "\n",
    "##### Exercice 5 : \n",
    "La suite de Syracuse est définie ainsi : \n",
    "\n",
    "A partir d'un premier terme entier naturel plus grand que $1$, on divise ce terme par $2$ s'il est pair, on le multiplie par $3$ et on ajoute $1$ s'il est impair. On recommence le même procédé pour obtenir les termes suivants.\n",
    "\n",
    "Pour un premier terme $s_0$ donné, on peut ainsi obtenir le terme de rang $n$ en écrivant la définition suivante :\n",
    "\n",
    "<center> $syracuse(n)=\\left\\{ \\begin{array}{lll} s_0 \\;si \\; n=0\\\\\n",
    "\\frac {syracuse(n-1)}{2} \\;si \\; syracuse(n-1)\\;est\\;pair\\\\\n",
    "3 \\times syracuse(n-1)+1 \\;si\\; syracuse(n-1)\\;est\\;impair \\end{array} \\right.$ </center>\n",
    "\n",
    "Compléter la fonction c-dessous à l'aide de cette définition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "s0=27\n",
    "\n",
    "def syracuse(n):\n",
    "    '''Calcul du terme de rang n\n",
    "    de la suite de Syracuse de premier terme u0\n",
    "    \n",
    "    parametres :  \n",
    "    u0 entier naturel > 1\n",
    "    n entier naturel\n",
    "    \n",
    "    return : \n",
    "    terme de rang n, entier naturel\n",
    "    '''\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "        \n",
    "assert(syracuse(6)==94)\n",
    "assert(syracuse(0)==s0)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Double récursion\n",
    "Les expressions qui définissent le ou les cas récursifs peuvent contenir plusieurs appels à la fonction que l'on est en train de définir."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Exercice 6 : \n",
    "Voici les premiers termes de la suite de Fibonacci : $1,1,2,3,5,8$. Elle est définie par ses deux premiers termes égaux à 1 et par le fait que chaque terme suivant s'obtient par la somme des deux précédents.\n",
    "\n",
    "Pour obtenir le terme de rang $n$, sa définition récursive est donc :\n",
    "\n",
    "\n",
    "<center> $fibonacci(n)=\\left\\{ \\begin{array}{ll} 1 \\;si \\; n \\leq 1\\\\\n",
    "fibonacci(n-1)+fibonacci(n-2) \\;si\\; n \\geq 2 \\end{array} \\right.$ </center>\n",
    "\n",
    "Compléter la fonction ci-dessous à l'aide de cette définition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibonacci(n):\n",
    "    '''Calcule le terme de rang n de la suite de Fibonacci\n",
    "    parametre : n entier naturel\n",
    "    return : le terme de rang n de la suite, entier naturel\n",
    "    '''\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "assert(fibonacci(0)==1)\n",
    "assert(fibonacci(1)==1)\n",
    "assert(fibonacci(5)==8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Récursion mutuelle\n",
    "On peut définir plusieurs fonctions récursives en même temps, quand ces fonctions font références les unes aux autres."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Exercice 7 :\n",
    "Voici une façon originale de définir la parité d'un nombre : un nombre pair(respectivement impair) est un nombre qui n'est pas impair(respectivement pair).\n",
    "\n",
    "On peut ainsi définir deux fonctions $pair(n)$ et $impair(n)$ qui s'appellent mutuellement !\n",
    "\n",
    "<table align='center' border='5' cellpadding='15'>\n",
    "<tr>\n",
    "<td>$pair(n)=\\left\\{ \\begin{array}{ll} True \\;si \\; n = 0\\\\\n",
    "impair(n-1) \\;si\\; n \\geq 1 \\end{array} \\right.$</td>\n",
    "<td>$impair(n)=\\left\\{ \\begin{array}{ll} False \\;si \\; n = 0\\\\\n",
    "pair(n-1) \\;si\\; n \\geq 1 \\end{array} \\right.$</td>\n",
    "</tr>\n",
    "</table>\n",
    "\n",
    "Compléter les deux fonctions ci-dessous à l'aide de la définition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pair(n):\n",
    "    '''renvoie True si n est pair,\n",
    "    False sinon'''\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "\n",
    "def impair(N):\n",
    "    '''renvoie True si n est impair,\n",
    "    False sinon'''\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "assert(pair(0)==True)\n",
    "assert(impair(0)==True)\n",
    "assert(pair(5)==False)\n",
    "assert(imparir(5)==True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Exécution des programmes\n",
    "Une fois que l'on a trouvé une définition récursive, la programmation avec Python est assez aisée. Pour éviter les valeurs absurdes, les erreurs, les boucles infinies ou le dépassement de capacité, il faut néanmoins faire attention à deux aspects:\n",
    "* Etre sûr que la définition est correctement formulée.\n",
    "* Veiller à ne pas saturer l'espace mémoire avec de trop nombreux appels."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bien écrire une définition récursive\n",
    "* Terminaison :Il faut être sûr que l'on va finir par arriver sur un cas de base de la définition.\n",
    "* Domaine de validité : Faire attention à ce que les valeurs utilisées lors des appels soient toujours dans le domaine de validité et qu'il y ait une définition pour toutes les valeurs du domaine."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Exercice 8 : \n",
    "Changeons la définition de la fonction $somme(n)$ et considérons que pour la calculer, il suffit d'ôter $n+1$ à $somme(n+1)$.\n",
    "\n",
    "<center> $somme(n)=\\left\\{ \\begin{array}{ll} 0 \\;si \\; n=0\\\\\n",
    "somme(n+1)-(n+1) \\;si\\; n>0 \\end{array} \\right.$ </center>\n",
    "\n",
    "Expliquer ce qui ne va pas dans cette définition."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Réponse : \n",
    "Pour calculer $somme(1)$, on va faire appel à $somme(2)$ qui va faire appel à $somme(3)$, etc. On ne retombe jamais sur le cas de base $n=0$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Exercice 9 :\n",
    "Voici la définition d'une fonction $g$ qui s'applique aux entiers naturels:\n",
    "\n",
    "<center> $g(n)=\\left\\{ \\begin{array}{ll} 1 \\;si \\; n=0\\\\\n",
    "n+g(n-2) \\;si\\; n>0 \\end{array} \\right.$ </center>\n",
    "\n",
    "Expliquer ce qui ne va pas dans cette définition."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Réponse :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Exercice 10 :\n",
    "Voici la définition d'une fonction $h$ qui s'applique aux entiers naturels:\n",
    "\n",
    "<center> $h(n)=\\left\\{ \\begin{array}{ll} 1 \\;si \\; n=0\\\\\n",
    "n+h(n-1) \\;si\\; n>1 \\end{array} \\right.$ </center>\n",
    "\n",
    "Expliquer ce qui ne va pas dans cette définition."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Réponse : \n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Nombre d'appels\n",
    "##### Exemple :\n",
    "Reprenons la suite de Fibonacci, que l'on notera ici $f$ pour plus de lisibilité pour la suite. Cette fonction est ici modifiée pour pouvoir se rendre compte des appels successifs effectués par python."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "f(6) f(5) f(5) f(4) f(4) f(3) f(3) f(2) f(2) f(1) f(1) f(0) f(1) f(1) f(1) f(1) f(0) f(1) f(1) f(2) f(1) f(1) f(0) f(1) f(1) f(1) f(3) f(2) f(2) f(1) f(1) f(0) f(1) f(1) f(1) f(1) f(0) f(1) f(1) f(4) f(3) f(3) f(2) f(2) f(1) f(1) f(0) f(1) f(1) f(1) f(1) f(0) f(1) f(1) f(2) f(1) f(1) f(0) f(1) f(1) f(1) "
     ]
    },
    {
     "data": {
      "text/plain": [
       "21"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def f(n):\n",
    "    '''Calcule le terme de rang n de la suite de Fibonacci\n",
    "    parametre : n entier naturel\n",
    "    return : le terme de rang n de la suite, entier naturel\n",
    "    '''\n",
    "    if n<=1:\n",
    "        print('f(1)', end=' ')\n",
    "        return 1\n",
    "    else:\n",
    "        print('f({})'.format(n-1), end=' ')\n",
    "        print('f({})'.format(n-2), end=' ')\n",
    "        return f(n-1)+f(n-2)\n",
    "    \n",
    "f(7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et voici l'arbre des appels pour $f(7)$ :\n",
    "<img src='fibo7.png' style='float:center;' width=100%>\n",
    "\n",
    "* Pour pouvoir effectuer ces calculs, l'espace mémoire est organisé sous forme d'une pile ou sont stockés les contextes d'éxécution de chaque appel de fonction(valeur de $n$, valeur de retour, opérations à effectuer...).\n",
    "\n",
    "* Dans le cas de $f(7)$, on constate que certains calculs apparaissent plusieurs fois. Par exemple, il y a 5 appels pour $f(3)$, ce qui signifie que cette valeur est calculée 5 fois par le programme et qu'il y a donc 5 emplacements mémoire où l'on trouve le même contexte nécéssaire au calcul !\n",
    "\n",
    "* Une définition récursive peut engendrer un grand nombre d'appels et donc occuper un espace mémoire important par la pile d'appels. Python limite par défaut le nombre d'appels autorisés à $1000$.D'autres langages, plus spécialisés dans ce type de programmation permettent de mieux gérer ces empilements d'appels.\n",
    "\n",
    "* Plus généralement, quand on écrit une fonction récursive , on cherche à choisir la bonne définition qui limite le nombre d'appels(voir exercice 14)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A retenir\n",
    "* Certains problèmes difficiles à résoudre peuvent être décrits à l'aide d'une définition récursive assez intuitive.\n",
    "* L'écriture d'une fonction récursive nécéssite de distinguer les cas de base, pour lesquels on donne un résultat facilement et les cas récursifs qui font appel à la fonction en cours de définition.\n",
    "* Il faut veiller à bien construire sa définition (terminaison, domaine de validité).\n",
    "* Il faut également avoir conscience que l'espace mémoire occupé peut rapidement devenir très important du fait des nombreux appels récursifs.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Exercices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Exercice 11: Puzzle algorithmique\n",
    " On considère un tournoi de $n$ équipes ($n \\geq 2$) dans lequel chaque équipe à rencontré exactement une fois chacune des autres équipes. Il n'y a pas de match nul. Est-il possible dans tous les cas de lister les équipes de telle sorte que chaque équipe a gagné le match contre l'équipe qui est listée juste après ? Justifier la réponse.\n",
    "\n",
    "\n",
    "Aide : La réponse est oui . On pourra répondre d'abord pour $n=2$, puis pour $n=3$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Réponse : "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Exercice 12 : Nombre de chiffres\n",
    "Compléter de façon récursive la fonction `n_chiffres(N)` ci-dessous qui renvoie le nombre de chiffres qui composent l'entier `N`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def n_chiffres(N):\n",
    "    '''\n",
    "    parametre :\n",
    "    un entier naturel N\n",
    "    \n",
    "    return :\n",
    "    le nombre de chiffres de N'''\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Exercice 13 : Les tours de Hanoi\n",
    "<img src='hanoi.png' style='float:right;' width=400>On considère $n$ disques de différentes tailles( $n \\geq 1$ ) et trois axes. Initialement, tous les disques sont sur le premier axe,  dans l’ordre croissant de leur taille, du plus grand en dessous jusqu'au plus petit sur le dessus. L’objectif est de transférer tous les disques sur un autre axe en un minimum de mouvements:\n",
    "* Un seul disque peut être déplacé à la fois.\n",
    "* Il est interdit de placer un disque plus grand sur un disque plus petit.\n",
    "\n",
    "1. Tester ce jeu pour $n=3$ ( http://championmath.free.fr/tourhanoi.htm) . On note $M(3)$ le nombre minimum de mouvements à effectuer pour déplacer trois disques. Que vaut $M(3) ?$\n",
    "\n",
    "\n",
    "<img src='hanoi_sol.png' style='float:right;' width=400>\n",
    "2. On note $M(n)$ le nombre minimum de mouvements nécéssaires pour déplacer $n$ disques. A l'aide de l'image ci-contre, exprimer $M(n)$ en fonction de $M(n-1)$.\n",
    "\n",
    "\n",
    "3. Compléter la fonction `M(n)` qui renvoie le nombre minimum de mouvements à effectuer pour déplacer `n` disques."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Réponses :\n",
    "1.  \n",
    "\n",
    "\n",
    "2.  \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n",
      "127\n"
     ]
    }
   ],
   "source": [
    "#3.\n",
    "def M(n):\n",
    "    '''Calcule le nombre minimal de mouvements\n",
    "    pour déplacer n disques'''\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "\n",
    "\n",
    "print(M(3))\n",
    "print(M(7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Exercice 14 : Exponentiation rapide\n",
    "Supposons que l'on dispose d'une fonction $carre(x)$ qui calcule le carré d'un nombre.\n",
    "\n",
    "Voici alors une autre définition pour $puissance(x,n)$ : \n",
    "\n",
    "<center> $puissance(x,n)=\\left\\{ \\begin{array}{lll} 1 \\;si \\; n=0\\\\\n",
    "carre(puissance(x,\\frac{n}{2})) \\;si \\; n \\geq 1 \\;et\\;pair\\\\\n",
    "x \\times carre(puissance(x,\\frac{n-1}{2}) \\;si \\; n \\geq 1 \\;et\\;impair \\end{array} \\right.$ </center>\n",
    "\n",
    "1. Compléter la fonction `puissance(x,n)` à l'aide de la définition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "#1. \n",
    "def carre(x):\n",
    "    '''calcule le carre de x\n",
    "    parametre : \n",
    "    x de type int ou float\n",
    "    \n",
    "    return :\n",
    "    le carre de x'''\n",
    "    \n",
    "    return x*x\n",
    "\n",
    "def puissance(x,n):\n",
    "    '''Calcule la puissance nième de x\n",
    "    paramètres : \n",
    "    x de type int ou float\n",
    "    n entier naturel\n",
    "    \n",
    "    return :\n",
    "    la puissance nième de x, de type int ou float\n",
    "    '''\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "assert(puissance(2,0)==1)\n",
    "assert(puissance(4,1)==4)\n",
    "assert(puissance(3,3)==27)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Modifier la fonction ci-dessous pour qu'elle puisse compter le nombre d'appels de la fonction `puissance`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "256 4\n"
     ]
    }
   ],
   "source": [
    "#2.\n",
    "\n",
    "N=1 #un compteur\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "   \n",
    "\n",
    "print(puissance(2,8),N)\n",
    "N=1 # on remet le compteur à 1 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. Combien d'appels de la fonction $puissance$ sont nécéssaires pour calculer :\n",
    "     * $x^{8}$ : \n",
    "     * $x^{15}$ : \n",
    "     * $x^{62}$ : \n",
    "     \n",
    "     \n",
    "4. Avec la définition de l'exercice 4, combien d'appels de la fonction $puissance$ sont nécéssaires pour calculer :\n",
    "     * $x^{8}$ : \n",
    "     * $x^{15}$ : \n",
    "     * $x^{62}$ : "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Exercice 15: Conjecture de Syracuse \n",
    "Le suite de Syracuse est la suite d'entiers $s_n$ définie par son premier terme $s_0 >1$ et par la relation de récurrence :\n",
    "\n",
    "<center> $s_n=\\left\\{ \\begin{array}{ll} \\frac{s_n}{2} \\;si \\; n\\;est\\;pair\\\\\n",
    "3s_n+1 \\;si\\; n\\;est\\;impair\\end{array} \\right.$ </center>\n",
    "\n",
    "La conjecture de Syracuse affirme que quelque soit la valeur de $s_0$, il existe un rang $n$ pour lequel $u_n=1$.cette conjecture n'a encore jamais été démontrée et défie les chercheurs du monde entier.\n",
    "\n",
    "Ecrire une fonction récursive `syracuse(u_n)` qui affiche les valeurs successives de `u_n` tant que `u_n` est plus grand que $1$. Tester ensuite différentes valeurs et constater cette conjecture."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def syracuse(u_n):\n",
    "    '''affiche les termes successifs de la suite de Syracuse\n",
    "    tant qu'ils sont supérieurs à 1.\n",
    "    parametre : u_n entier, premier terme de la suite\n",
    "    sortie : affichage des termes successifs'''\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "        \n",
    "syracuse(27)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Exercice 16 : La fractale de Koch\n",
    "<img src='koch.png' style='float:center;' width=100%>\n",
    "La fractale de Koch peut s'obtenir de manière récursive:\n",
    "\n",
    "* Le cas de base à l'ordre $0$ est un segment de longueur $l$.\n",
    "* Le cas récursif d'ordre $n$ s'obtient en divisant ce segment en trois morceaux de même longueur $\\frac{l}{3}$, puis en dessinant un triangle équilatéral dont la base est le morceau du milieu(cette base n'est pas dessinée).\n",
    "\n",
    "Ci-dessus les courbes d'ordre $0$,$1$,$2$ et $3$ sont dessinées respectivement de gauche à droite.\n",
    "\n",
    "Compléter la fonction `koch(n,l)` qui dessine la fractale de Koch de profondeur `n` à partir d'u segment de longueur `l`, à l'aide du module `turtle`.\n",
    "\n",
    "Mémo turtle :\n",
    "\n",
    "* `forward(l)` : la tortue avance de $l$ pixels dans le sens ou elle est orientée\n",
    "* `left(60)` : la tortue tourne sur elle même vers la gauche d'un angle $a$ en degrés"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "from turtle import *\n",
    "\n",
    "def koch(n,l):\n",
    "    '''dessine un flocon de koch\n",
    "    de profondeur n, a partir d'un \n",
    "    segment de longueur l'''\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "koch(3,200)    \n",
    "mainloop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Exercice 17 : Triangle de Sierpinsky (DM ?)\n",
    "<img src='sierpinsky.png' style='float:right;' width=300>\n",
    "\n",
    "* https://fr.wikipedia.org/wiki/Triangle_de_Sierpi%C5%84ski\n",
    "\n",
    "Ecrire la fonction récursive `sierpinsky(n,l)` qui dessine le triangle de Sierpinsky à l'ordre $n$ à partir d'un segment de longueur $l$. Ci-dessus, le résultat de `sierpinsky(5,300)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [],
   "source": [
    "from turtle import *\n",
    "\n",
    "def sierpinsky(n,l):\n",
    "    '''trace un triangle de sierpinsky\n",
    "    apres n itérations, à partir d'un\n",
    "    triangle equilatéral de côté l\n",
    "    '''\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "        \n",
    "        \n",
    "hideturtle()        \n",
    "speed('fastest')\n",
    "sierpinsky(5,300)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <center> FIN</center>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}