Tnsi_recurrence.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Tnsi_recurrence.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyMcRm7CvKr6fYVzoqgLxCnl",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/srenouf/Tnsi/blob/master/Tnsi_recurrence.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yomykPef4OiF"
      },
      "source": [
        "\n",
        "\n",
        "---\n",
        "# RECURSIVITE\n",
        "\n",
        "\n",
        "---\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IzgADsGa2pf5"
      },
      "source": [
        "##Introduction : <br>\n",
        "Une des premières choses que l'on apprend lorsqu'on commence à programmer est la notion de boucle : on a souvent besoin dans un algorithme de répéter une partie du programme. On parle alors de **programmation itérative**.\n",
        "\n",
        "Observons l'algorithme d'Euclide permettant de trouver le PGCD de deux entiers : Vous avez probablement utilisé une boucle Tant que pour implémenter cet algorithme. En voici une version simple sachant que $pgcd(a,b)=pgcd(b, reste \\ de\\  la \\ division \\ euclidienne\\ de\\ a \\  par \\ b)$"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yX2J6Dwq28E_"
      },
      "source": [
        "def pgcd(a, b):\n",
        "    while b>0:\n",
        "        a, b = b, a%b\n",
        "    return a"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pCBWJ6QI3fBx"
      },
      "source": [
        "Tester le programme en calculant pgcd(5,25) puis pgcd(124,44)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lupkekss4WrH"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oHVgysAq3vJR"
      },
      "source": [
        "cet algorithme s'arrête car a%b est un entier naturel strictement inférieur à b donc à un moment donné ce reste sera nul c'est à dire a est divisible par b. Vous voyez que la manière la plus simple et naturelle d'énoncer cet algorithme est de définir le pgcd par le pgcd lui même !"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SnMuQb-P38R3"
      },
      "source": [
        "**Lorsque la définition d'un objet fait appel à l'objet lui même, on parle de définition récursive.** \n",
        "<br><br>\n",
        "*Exemples : *:\n",
        "<img src=\"https://www.apprendre-en-ligne.net/blog/images/vaches/vache111.jpg\">  blog de Didier Muller\n",
        "<br>\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1nEgxA8Q3eh1",
        "outputId": "29ac958a-629f-48f9-e9a6-2089065ec2b0",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 336
        }
      },
      "source": [
        "%%html\n",
        "<iframe width=\"560\" height=\"315\" src=\"https://www.youtube.com/embed/iFA3g_4myFw\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen></iframe>"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/html": [
              "<iframe width=\"560\" height=\"315\" src=\"https://www.youtube.com/embed/iFA3g_4myFw\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen></iframe>"
            ],
            "text/plain": [
              "<IPython.core.display.HTML object>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "W-palQwi5ZkX"
      },
      "source": [
        "En informatique<br>\n",
        "\n",
        "Vous l'avez compris, la récursivité est partout, et donc bien sûr en informatique. Les premiers langages de programmation qui ont autorisé l'emploi de la récursivité sont LISP et Algol 60. Dans LISP, elle est tellement fondamentale que ce langage ne possède pas de structures de boucles ! tout se fait avec la récursivité !<br>\n",
        "\n",
        "Tous les langages de programmation haut niveau peuvent utiliser la récursivité, c'est à dire la faculté que possède une fonction à s'appeler elle-même"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RvCazBqx5iE5"
      },
      "source": [
        "# Ecrire des fonctions récursives"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nsecl70x6wiA"
      },
      "source": [
        "En Python, l’implémentation d’une fonction récursive est semblable à celle des autres fonctions, à ceci près qu’une fonction récursive doit impérativement contenir un retour avec le mot clé return pour faire les appels récursifs.\n",
        "<br><br>\n",
        "\n",
        "\n",
        "---\n",
        "\n",
        "Méthode\n",
        "\n",
        "---\n",
        "<br>\n",
        "Lorsque l’on écrit une fonction récursive en Python, on peut partager son code en deux parties :<br>\n",
        "\n",
        "*   une condition d’arrêt pour stopper les appels récursifs ;\n",
        "*   les appels récursifs\n",
        "\n",
        "<br>\n",
        "Lors de l’exécution, les appels récursifs successifs sont stockés dans une pile, c’est la pile d’exécution. \n",
        "Plus précisément, la pile d’exécution est un emplacement mémoire destiné à stocker les paramètres, les variables locales ainsi que les adresse mémoires de retour des fonctions en cours d’exécution. On parle d'arbre d'exécution de l'algorithme.\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GlvOuwnG8tSe"
      },
      "source": [
        "Exemple 1 : la factorielle de $n$ notée $n!$<br>\n",
        "La factorielle d’un nombre est le produit d’un nombre entier et de tous les nombres inférieurs, par exemple, la factorielle de 4 est 4 * 3 * 2 * 1 = 24. <br>\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qM77xBTp9TgG"
      },
      "source": [
        "Voici en python la fonction récursive permettant de faire les calculs, exécutez le code et calculez factorielle(5)."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "M_H2El7x61fK"
      },
      "source": [
        "def factorielle(n):\n",
        "    \"\"\"fonction récursive qui appelle\n",
        "   lui-même pour trouver la factorielle du nombre donné\"\"\"\n",
        "    if n == 1:\n",
        "        return n\n",
        "    else:\n",
        "        return n * factorielle(n - 1)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ee9PDkKo9jd5"
      },
      "source": [
        "Voici l'arbre d'exécution de l'algorithme:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GA6ukFL18c7D"
      },
      "source": [
        "<img src=\"https://www.enib.fr/enibook/algorithmic/learning/site/html/_images/recursivite-factorielle-1.png\">"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ppitgJVO9vQ1"
      },
      "source": [
        "essayez différentes valeurs pour la factorielle. Trouvez à partir de quelle valeurs, il y a un problème. Donnez la nature de ce problème.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MpY-ZL4O-BtI"
      },
      "source": [
        "Par défaut,\n",
        "le nombre maximum d’appels récursifs autorisés est fixé à 1000, exécutez le code suivant et retestez la fonction factorielle avec des valeurs de $n$ plus grande.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "npS1_PXx-wxf"
      },
      "source": [
        "import sys\n",
        "sys.setrecursionlimit(5000) \n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bLNKf6LJ_Hc4"
      },
      "source": [
        "#A vous de jouer!\n",
        "<br>\n",
        "La suite de Fibonacci est la suite de nombres entiers 1 - 1 - 2 - 3 - 5 - 8 - .... <br>\n",
        "En pratique, on obtient un élément de la suite en additionnant les deux termes précédents. <br>\n",
        "Programmer une fonction fibonacci de manière récursive.<br>\n",
        "Programmer une fonction fibonacci_iterative<br>\n",
        "Tester les deux manières de procéder.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kmhp5dpXCe6A"
      },
      "source": [
        "Et les fractales dans tout cela!<br>\n",
        "Rechercher la fractale de sierpinski. Réfléchir à une construction récursive, en la construisant à la main pour $n=2$ et $n=3$. Puis écrire une fonction python récursive permettant de la créer. On utilisera la cellule trinket ci-dessous, il ne faudra pas oublier de télécharger votre code python^^"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EMRFueH-_HMD",
        "outputId": "1be14628-f74c-4d41-fc2e-0958c6d13389",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 377
        }
      },
      "source": [
        "%%html\n",
        "\n",
        "\n",
        "<iframe src=\"https://trinket.io/embed/python3/6d1226a5c9\" width=\"100%\" height=\"356\" frameborder=\"0\" marginwidth=\"0\" marginheight=\"0\" allowfullscreen></iframe>\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/html": [
              "\n",
              "\n",
              "<iframe src=\"https://trinket.io/embed/python3/6d1226a5c9\" width=\"100%\" height=\"356\" frameborder=\"0\" marginwidth=\"0\" marginheight=\"0\" allowfullscreen></iframe>"
            ],
            "text/plain": [
              "<IPython.core.display.HTML object>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    }
  ]
}