2015-12-02 - TD15 - Révisions sur la récursivité.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Préambule :** nous avons commencé par faire un rappel sur la récursivité en ré-écrivant le comportement de factorielle au tableau et en déroulant l'algorithme à la main. \n",
    "\n",
    "Nous rappelons qu'une fonction récursive est une fonction qui s'appelle elle-même. Chaque appel à la fonction est indépendant des autres. Le moyen le plus simple pour réussir l'écriture d'une fonction récursive est de toujours commencer par exprimer le cas simple (la solutiotin immédiate), puis d'écrire le cas récursif (la solution qui fait appel à la solution plus simple).\n",
    "\n",
    "Ci-dessous, vous trouverez le squelette d'une fonction récursive typique. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (<ipython-input-1-974b6aeadca3>, line 1)",
     "output_type": "error",
     "traceback": [
      "\u001b[1;36m  File \u001b[1;32m\"<ipython-input-1-974b6aeadca3>\"\u001b[1;36m, line \u001b[1;32m1\u001b[0m\n\u001b[1;33m    if (cas simple):\u001b[0m\n\u001b[1;37m                 ^\u001b[0m\n\u001b[1;31mSyntaxError\u001b[0m\u001b[1;31m:\u001b[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "if (cas simple):\n",
    "    (solution immédiate)\n",
    "else:\n",
    "    (solution récursive,\n",
    "     impliquant un cas plus simple que le problème original)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercice Robozzle :** nous avons ensuite résolu l'exercice Robozzle n°656, l'objectif était de vous faire comprendre le fonctionnement de la pile d'appels récursifs. http://robozzle.com/js/play.aspx?puzzle=656"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--- fact(1) = 1\n",
      "--- fact(2) = 2\n",
      "--- fact(3) = 6\n",
      "--- fact(4) = 24\n",
      "--- fact(5) = 120\n",
      "--- fact(6) = 720\n",
      "720\n"
     ]
    }
   ],
   "source": [
    "def fact(n):\n",
    "    \"\"\"\n",
    "    :entrée n: int\n",
    "    :pré-cond: n > 0\n",
    "    :sortie f: int\n",
    "    :post-cond: f = n * (n-1) * ... * 1\n",
    "    \"\"\"\n",
    "    if n == 1:\n",
    "        f = 1\n",
    "    else:\n",
    "        f = fact(n-1)*n\n",
    "    print(\"--- fact({}) = {}\".format(n,f))\n",
    "    return f\n",
    "\n",
    "print(fact(6))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Vous cherchez d'autres idées pour vous entraîner à la récursivité ? Proposez donc l'algorithme de puissance, celui de Fibonacci ou encore le triangle de Pascal en récursif. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}