TP-Récursivité.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TP Récursivité\n",
    "Vous avez normalement lu et éxécuté le cours et les exemples de cette page : https://pixees.fr/informatiquelycee/n_site/nsi_term_fctRec.html\n",
    "\n",
    "Dans ce TP, nous allons continuer à programmer des exemples de façon récursive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Partie 1 - Avec des figures géométriques\n",
    "## Exercice 1\n",
    "Voici un code qu'on peut éxécuter avec turtle : (à noter que vous devez copier ce code dans un environnement qui supporte turtle comme replit.com sur un repl python+turtle ou bien sur spyder. Vous pouvez également utiliser ColabTurtle directement depuis un Google Colab, comme dans l'exemple suivant : https://colab.research.google.com/github/karinjd/CSCI5525/blob/master/Turtle.ipynb   )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "import turtle as t\n",
    "\n",
    "def koch(longueur, n):\n",
    "    if n == 0:\n",
    "        t.forward(longueur)\n",
    "    else:\n",
    "        koch(longueur/3, n-1)\n",
    "        t.left(60)\n",
    "        koch(longueur/3, n-1)\n",
    "        t.right(120)\n",
    "        koch(longueur/3, n-1)\n",
    "        t.left(60)\n",
    "        koch(longueur/3, n-1)\n",
    "\n",
    "def flocon(taille, etape):\n",
    "    koch(taille, etape)\n",
    "    t.right(120)\n",
    "    koch(taille, etape)\n",
    "    t.right(120)\n",
    "    koch(taille, etape)\n",
    "\n",
    "flocon(100, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On voit bien la récursivité dans ce code car la fonction Koch appelle la fonction Koch elle-même...\n",
    "\n",
    "Voici un autre exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import turtle as t\n",
    "\n",
    "def carre(longueur):\n",
    "    for i in range(4):\n",
    "        t.forward(longueur)\n",
    "        t.left(90)\n",
    "        \n",
    "def carresimbriques_imp(taille, etape):\n",
    "    for i in range(etape):\n",
    "        carre(taille)\n",
    "        taille=taille-10\n",
    "\n",
    "carresimbriques(100, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On voit dans cet exemple que les carrés imbriqués sont appelés dans une boucle mais il n'y a pas de récursivité car aucune fonction ne s'appelle elle-même!\n",
    "Vous devez donc réécrire la fonction carresimbriques pour qu'elle soit récursive et se comporte exactement comme dans l'exemple ci-dessus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "import turtle as t\n",
    "\n",
    "def carre(longueur):\n",
    "    for i in range(4):\n",
    "        t.forward(longueur)\n",
    "        t.left(90)\n",
    "        \n",
    "def carresimbriques_rec(taille, etape):\n",
    "    ####a modifier\n",
    "    return\n",
    "\n",
    "carresimbriques_rec(100, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 2\n",
    "De la même façon, écrivez une fonction récursive permettant de tracer une spirale carrée comme le fait le code suivant :\n",
    "\n",
    "### version impérative"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import turtle as t\n",
    "\n",
    "def boutdespirale(longueur):\n",
    "    t.forward(longueur)\n",
    "    t.left(90)\n",
    "        \n",
    "def spirale_imp(taille):\n",
    "    while taille>0:\n",
    "        boutdespirale(taille)\n",
    "        taille=taille-10\n",
    "\n",
    "spirale_imp(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Version récursive"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import turtle as t\n",
    "\n",
    "def spirale_rec(taille):\n",
    "## a faire\n",
    "spirale_rec(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Partie 2 - Avec des nombres\n",
    "## Exercice 3\n",
    "Écrire une fonction somme qui prend deux entiers en entrée en renvoie la somme de ces deux entiers en sortie.\n",
    "Une contrainte toutefois : la fonction doit-être récursive et on suppose que seules les opérations +1 et -1 sont permises sur les nombres."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "à faire\n"
     ]
    }
   ],
   "source": [
    "def somme(a,b):\n",
    "    #c'est cette fonction qu'il faut coder \n",
    "    return \"à faire\"\n",
    "\n",
    "print(somme(3,5)) #doit renvoyer 8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 4 - Algorithme d'Euclide\n",
    "L'algorithme d'Euclide permet de calculer le pgcd de deux nombres entiers,c'est à dire le plus grand entier positif divisant ces deux nombres,par des divisions successives.\n",
    "\n",
    "Voici le déroulement de cet algorithme pour le calcul du pgcd de $a= 119$ et $b= 544$ :\n",
    "\n",
    "$544 = 119 \\times 4 + 68$ (quotient 4, reste 68)\n",
    "\n",
    "$119 = 68 \\times 1 + 51$ (quotient 1, reste 51)\n",
    "\n",
    "$68 = 51 \\times 1 + 17$ (quotient 1, reste 17)\n",
    "\n",
    "$51 = 17 \\times 3 + 0$ (quotient 3, reste 0)\n",
    "\n",
    "Le dernier reste non nul est 17, c'est le PGCD de 119 et 544\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "On rappelle les opérations de divisions sur les entiers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.571428571428571\n",
      "4\n",
      "68\n"
     ]
    }
   ],
   "source": [
    "print(544/119)    # division flottante\n",
    "print(544//119)   # division entiere : quotient\n",
    "print(544%119)    # division entiere : reste"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "À vous de programmer de façon impérative et récursive l'algorithme d'Euclide..\n",
    "\n",
    "### Version impérative"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "à faire\n"
     ]
    }
   ],
   "source": [
    "def pgcd_imp (a,b):\n",
    "    # a faire\n",
    "    return (\"à faire\")\n",
    "\n",
    "print(pgcd_imp (544,119)) #renvoie 17"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Version récursive"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "à faire\n"
     ]
    }
   ],
   "source": [
    "def pgcd_rec (a,b):\n",
    "    # à faire\n",
    "    #return pgcd(d'autres paramètres)\n",
    "    return \"à faire\"\n",
    "\n",
    "print(pgcd_rec (544,119)) #renvoie 17"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 5 - Suite de Fibonacci\n",
    "La suite de Fibonacci est une suite définie par récurrence comme suit :\n",
    "\n",
    "$\n",
    "\\left\\{\n",
    "    \\begin{array}{ll}\n",
    "        u_0=1 \\\\\n",
    "        u_1=1 \\\\\n",
    "        u_{n+2}=u_n+u_{n+1}\n",
    "    \\end{array}\n",
    "\\right.\n",
    "$\n",
    "\n",
    "Autrement dit, c'est une suite commençant par 1 et 1 et dont les termes suivants sont calculés en faisant la somme des deux termes précédents. Les premiers termes de cette suite sont donc 1,1,2,3,5,8,13,...\n",
    "\n",
    "Implémentez cette suite de Fibonacci de façon impérative et récursive."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "à faire\n",
      "à faire\n"
     ]
    }
   ],
   "source": [
    "def fibo_imp(n):\n",
    "    #Affiche le n-ème terme de la suite de Fibonacci, on suppose que n>=2\n",
    "    # A FAIRE\n",
    "    return \"à faire\"\n",
    "    \n",
    "def fibo_rec(n):\n",
    "    #Affiche le n-ème terme de la suite de Fibonacci, on suppose que n>=2\n",
    "    # A FAIRE\n",
    "    return \"à faire\"\n",
    "    \n",
    "print(fibo_imp(5))  #doit afficher 5\n",
    "print(fibo_rec(5))  #doit afficher 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}