CH1 Programmation fonctionnelle et récursivité #2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CH1 Programmation fonctionnelle et récursivité #2 : LA RECURSIVITE\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Découverte\n",
    "\n",
    "### 1.a Une fonction peut en appeler une autre (c'est même très fréquent)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def foo(a):\n",
    "    return 2*a\n",
    "def bar(a):\n",
    "    return foo(a+2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "14"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bar(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remarque : les environnements des fonctions successives sont stockés dans une pile d'exécution (call - stack)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.b Une fonction peut-elle s'appeler elle-même ?\n",
    "Une fonction qui s'appelle elle-même est une fonction récursive "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def auto(a):\n",
    "    return auto(a)+2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "ename": "RecursionError",
     "evalue": "maximum recursion depth exceeded",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mRecursionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-2-0b3adc20f0d7>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mauto\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m5\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-1-0c75996908d2>\u001b[0m in \u001b[0;36mauto\u001b[1;34m(a)\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;32mdef\u001b[0m \u001b[0mauto\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ma\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m     \u001b[1;32mreturn\u001b[0m \u001b[0mauto\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ma\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m+\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "... last 1 frames repeated, from the frame below ...\n",
      "\u001b[1;32m<ipython-input-1-0c75996908d2>\u001b[0m in \u001b[0;36mauto\u001b[1;34m(a)\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;32mdef\u001b[0m \u001b[0mauto\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ma\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m     \u001b[1;32mreturn\u001b[0m \u001b[0mauto\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ma\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m+\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mRecursionError\u001b[0m: maximum recursion depth exceeded"
     ]
    }
   ],
   "source": [
    "auto(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cet appel crée une boucle sans terminaison. Une interruption du noyau est nécessaire."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.c Une utilisation astucieuse de la récursivité : La fonction factorielle.\n",
    "\n",
    "On a vu que `` n! = n x (n-1) x (n-2) x ... x 1 ``\n",
    "\n",
    "\n",
    "On peut aussi donner une définition récursive de cette opération\n",
    "`` n! = n x (n-1)! ``\n",
    "\n",
    "mais il ne faut pas oublier ``1! = 1`` sinon la définition boucle elle aussi !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorielle(n):\n",
    "    #print('factorielle de ',n,' appelé')\n",
    "    if n==1:\n",
    "        return 1\n",
    "    else:\n",
    "        return n*factorielle(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factorielle(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La terminaison de la boucle récursive est assurée par la décroissance de l'argument (Détailler la pile d'exécution), la correction est assurée par la fidélité à la définition vue plus haut."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. La recherche dichotomique avec la récursivité (BAC)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 4, 4, 5, 6, 6, 8, 9, 9, 10, 11, 12, 12, 15, 16, 17, 17, 21, 22, 23, 23, 24, 25, 25, 25, 26, 26, 27, 28, 29, 32, 34, 36, 37, 40, 42, 48, 48, 50, 52, 55, 55, 56, 56, 56, 56, 57, 57, 58, 59, 59, 59, 63, 63, 63, 63, 64, 66, 67, 67, 67, 68, 70, 70, 71, 72, 73, 74, 74, 75, 76, 76, 77, 80, 81, 82, 83, 84, 85, 86, 86, 87, 87, 87, 87, 89, 89, 89, 90, 92, 92, 93, 94, 95, 96, 97, 99, 99, 99, 100]\n"
     ]
    }
   ],
   "source": [
    "t=[random.randint(1,100) for i in range(100)]\n",
    "t.sort()\n",
    "print(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dicho(e,t,min,max):\n",
    "    ''' recherche par dichotomie de l'élément e dans le tableau t entre les indices min et max\n",
    "        entrée : e,t,min,max\n",
    "        sortie : index de l'élément, -1 sinon\n",
    "    '''\n",
    "    print(min,max)\n",
    "    # terminaison 1\n",
    "    if min>max:\n",
    "        return -1\n",
    "    mil = (max + min) //2\n",
    "    if t[mil]==e: # terminaison 2\n",
    "        return mil\n",
    "    elif t[mil]<e:\n",
    "        return dicho(e,t,mil+1,max)\n",
    "    else:\n",
    "        return dicho(e,t,min,mil-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 99\n",
      "0 48\n",
      "25 48\n",
      "37 48\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dicho(56,t,0,len(t)-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Une belle utilisation de la récursivité : la fractale de Von Koch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "ename": "ModuleNotFoundError",
     "evalue": "No module named 'mobilechelonian'",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mModuleNotFoundError\u001b[0m                       Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-16-7fb43f4db258>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[1;32mfrom\u001b[0m \u001b[0mmobilechelonian\u001b[0m \u001b[1;32mimport\u001b[0m \u001b[0mTurtle\u001b[0m  \u001b[1;31m#necessite l'importation du module mobilechelonian dans votre environnement jupyter notebook\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      2\u001b[0m \u001b[1;31m# via la commande pip install mobilechelonian\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mModuleNotFoundError\u001b[0m: No module named 'mobilechelonian'"
     ]
    }
   ],
   "source": [
    "from mobilechelonian import Turtle  #necessite l'importation du module mobilechelonian dans votre environnement jupyter notebook\n",
    "# via la commande pip install mobilechelonian"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "os.environ['http_proxy'] = \"http://192.168.1.10:80\" "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Collecting package metadata: ...working... failed\n",
      "\n",
      "Note: you may need to restart the kernel to use updated packages.\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING: The conda.compat module is deprecated and will be removed in a future release.\n",
      "\n",
      "CondaHTTPError: HTTP 000 CONNECTION FAILED for url <https://repo.anaconda.com/pkgs/r/win-64/repodata.json.bz2>\n",
      "Elapsed: -\n",
      "\n",
      "An HTTP error occurred when trying to retrieve this URL.\n",
      "HTTP errors are often intermittent, and a simple retry will get you on your way.\n",
      "\n",
      "If your current network has https://www.anaconda.com blocked, please file\n",
      "a support request with your network engineering team.\n",
      "\n",
      "SSLError(MaxRetryError('HTTPSConnectionPool(host=\\'repo.anaconda.com\\', port=443): Max retries exceeded with url: /pkgs/r/win-64/repodata.json.bz2 (Caused by SSLError(SSLError(\"bad handshake: Error([(\\'SSL routines\\', \\'tls_process_server_certificate\\', \\'certificate verify failed\\')])\")))'))\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "conda install mobilechelonian"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def courbe_koch(longueur, etape):\n",
    "    # fonction récursive qui dessine un \"côté\" du triangle de Von Koch \n",
    "    \n",
    "    if etape == 0: # terminaison de la récursivité\n",
    "        turtle.forward(longueur)\n",
    "    else:\n",
    "        courbe_koch(longueur/3, etape-1)\n",
    "        turtle.left(60)\n",
    "        courbe_koch(longueur/3, etape-1)\n",
    "        turtle.right(120)\n",
    "        courbe_koch(longueur/3, etape-1)\n",
    "        turtle.left(60)\n",
    "        courbe_koch(longueur/3, etape-1)\n",
    "        \n",
    "def flocon_koch(longueur, etape):\n",
    "    \"\"\"Fonction pour dessiner un flocon de Von Koch\n",
    "    depuis le coin haut gauche\"\"\"\n",
    "    for i in range(3):  #Pour chaque côté du triangle initial\n",
    "        courbe_koch(longueur, etape)  #Courbe de Von Koch\n",
    "        turtle.right(120)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "2082fd87c65241d5acedf6d92b48f6d1",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Turtle()"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "turtle = Turtle()\n",
    "turtle.speed(20)\n",
    "turtle.penup()\n",
    "turtle.setposition(10,100)\n",
    "turtle.pendown()\n",
    "flocon_koch(250, 4)"
   ]
  },
  {
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}