{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1> Complément sur la récursivité </h1>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2> 1. Récursivité multiple </h2>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Activité </h3>\n",
    "<p> La suite de Fibonnacci est une suite de nombres dont chacun est la somme des deux précédents.<br> Le premier et le second nombres sont égaux à 1. <br>On obtient la suite de nombres : 1 - 1 - 2 - 3 - 5 - 8 - 13 - 21 - ... </p>\n",
    "\n",
    "<p> Mathématiquement, cette suite notée (Fn) est donc définie par : </p>\n",
    "<ul> <li> F<sub>0</sub> = 1 </li>\n",
    "    <li> F<sub>1</sub> = 1 </li>\n",
    "    <li> F<sub>n</sub>= F<sub>n-1</sub> + F<sub>n-2</sub> </li>\n",
    "</ul>\n",
    "<h5> Question 1 :</h5> <p> Ecrivez une fonction récursive fibo(n) qui renvoie le terme de rang n de cette suite. Attention : il y a deux cas de base. </p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1b47b2c4",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h4>  On parle ici de récursivité multiple puisque chaque appel entraîne plusieurs appels récursifs (deux !). </h4>\n",
    "<h5> Question 2 :</h5> sur feuille , écrire l'exécution de l'appel de  fibo(4) en utilisant la présentation donnée dans le cours. <br>Soyez rigoureux car chaque appel récursif génère deux appels récursifs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h5> Exercice 11 </h5> Complèter le code de la fonction récursive qui recherche le minimum d'une tableau T en appliquant le principe de la dichotomie </li>\n",
    "  </ul>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "3d8cd70e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rech_min_rec(T):\n",
    "    il len(T)==...:\n",
    "        return ....\n",
    "    else:\n",
    "        a= .....\n",
    "        b= .....\n",
    "        if a>b:\n",
    "            return b\n",
    "        else:\n",
    "            return a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2> 2. Récursivité terminale </h2>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p> Un algorithme récursif simple est <strong>terminal </strong> lorsque l’appel récursif est le dernier calcul effectué pour obtenir le résultat. <br> Il n’y a pas de \"calcul en attente\". L’avantage est qu’il n’y a rien à mémoriser dans la pile.</p>\n",
    "\n",
    "<p> Pour rendre terminal un algorithme récursif, on utilise un accumulateur placé en paramètre.<br>\n",
    "Voici la fonction factorielle en récursivité terminale :</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "faaf421d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fact_term(n, acc = 1):\n",
    "    if n <= 1:\n",
    "        return acc\n",
    "    else:\n",
    "        return fact_term(n-1, acc * n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p> Une autre définition possible de fonction f  récursive terminale  est quand tout appel récursif est de la forme return f(...); sans qu'il n'y ait aucune opération sur cette valeur. </p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h5> Exercice 13 </h5>\n",
    "soit la fonction occ(c,s) qui compte le nombre d'occurences du caractère c dans le mot mot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f1f9e5da",
   "metadata": {},
   "outputs": [],
   "source": [
    "def occ(c,mot):\n",
    "    if len(mot) == 0:\n",
    "        return 0\n",
    "    elif c == mot[0]:\n",
    "        return 1 + occ(c,mot[1:])\n",
    "    else:\n",
    "        return occ(c,mot[1:])\n",
    "\n",
    "assert occ(\"e\",\"combien de e dans cette phrase ?\")==6\n",
    "assert occ(\"e\",\"la disparition\")==0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p> Ecrire occt une fonction version récursif terminal de la fonction occ </p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5db2890e",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "29469f30",
   "metadata": {},
   "source": [
    "<h5> Exercice 14 </h5>\n",
    "Ecrire la fonction de Fibonnacci en récursivité terminale puis comparer la rapidité d'execution avec la recursivité classique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "e25bb785",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibo2():\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2>3. Récursivité croisée </h2>\n",
    "<p> On parle de récursivité croisée lorsque deux fonctions s’appellent l’une l’autre récursivement.</p>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "614101d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exemple typique (et très classique) :\n",
    "def pair(n):\n",
    "    if n == 0:\n",
    "        return True\n",
    "    else:\n",
    "        return impair(n-1)\n",
    "\n",
    "def impair(n):\n",
    "    if n == 0:\n",
    "        return False\n",
    "    else:\n",
    "        return pair(n-1)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Détailler sur feuille l'appel de fonction :  pair(7)"
   ]
  }
 ],
 "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.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}