{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "069061e7",
   "metadata": {},
   "source": [
    "# Algorithmes récursifs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c052fd30",
   "metadata": {},
   "outputs": [],
   "source": [
    "from utils import *"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea0bdca5",
   "metadata": {},
   "source": [
    "## Calcul récursif de la factorielle\n",
    "\n",
    "La factorielle de $n \\in \\mathbb{N}$ est définie par: $n! = 1 \\times \\ldots \\times n$. On en déduit une définition récursive, $n!$ est le terme de rang $n$ de la suite définie par:\n",
    "- $u_0 = 1$\n",
    "- $u_n = u_{n-1} \\times n$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5e85f6ec",
   "metadata": {},
   "outputs": [],
   "source": [
    "@trace\n",
    "def factorielle(n: int) -> int:\n",
    "    assert n >= 0\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return factorielle(n - 1) * n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "be3544e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "factorielle(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ce47aa01",
   "metadata": {},
   "source": [
    "## Suite de Fibonacci\n",
    "\n",
    "Mettre en oeuvre un algorithme récursif qui calcule le terme de rang $n \\in \\mathbb{N}$ de la suite de Fibonacci:\n",
    "- $F_0 = 0$\n",
    "- $F_1 = 1$\n",
    "- $F_n = F_{n-1} + F_{n-2}$ pour $n \\ge 2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6edd6a4a",
   "metadata": {},
   "outputs": [],
   "source": [
    "@trace\n",
    "def fibonacci(n: int) -> int:\n",
    "    assert n >= 0\n",
    "    if n <= 1:\n",
    "        return n\n",
    "    else:\n",
    "        return fibonacci(n-1) + fibonacci(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "52f01b3f",
   "metadata": {},
   "outputs": [],
   "source": [
    "fibonacci(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99292c92",
   "metadata": {},
   "source": [
    "## Calcul des termes d'une suite arithmétique\n",
    "\n",
    "Suite arithmétique de raison $r$ et de premier terme $p$:\n",
    "- $u_0 = p$\n",
    "- $u_n = u_{n-1} + r$ pour $n \\ge 1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1d2b69c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "@trace\n",
    "def arithmetique(n: int, r: int, p: int) -> int:\n",
    "    assert n >= 0\n",
    "    if n == 0:\n",
    "        return p\n",
    "    else:\n",
    "        return arithmetique(n-1, r, p) + r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c03de1ca",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Suite des entiers naturels impairs\n",
    "# u0 = 1\n",
    "# u{n} = u{n-1} + 2\n",
    "\n",
    "arithmetique(5, r=2, p=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c7af6e7",
   "metadata": {},
   "source": [
    "## Calcul des termes d'une suite géométrique\n",
    "\n",
    "Suite géométrique de raison $r$ et de premier terme $p$:\n",
    "- $u_0 = p$\n",
    "- $u_n = r \\cdot u_{n-1}$ pour $n \\ge 1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "efedfca3",
   "metadata": {},
   "outputs": [],
   "source": [
    "@trace\n",
    "def geometrique(n: int, r: int, p: int) -> int:\n",
    "    assert n >= 0\n",
    "    if n == 0:\n",
    "        return p\n",
    "    else:\n",
    "        return geometrique(n-1, r, p) * r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "401ce32f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Suite des puissances de 2\n",
    "# u0 = 1\n",
    "# u{n} = 2 * u{n-1}\n",
    "\n",
    "geometrique(5, r=2, p=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "17018041",
   "metadata": {},
   "source": [
    "## Calcul de puissance\n",
    "\n",
    "Écrire une fonction récursive qui calcule $x^n$ pour un nombre flottant $x$ et un entier naturel $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "768c1dce",
   "metadata": {},
   "outputs": [],
   "source": [
    "@trace\n",
    "def puissance(x: float, n: int) -> float:\n",
    "    assert n >= 0\n",
    "    if n == 0:\n",
    "        return 1.0\n",
    "    else:\n",
    "        return x * puissance(x, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "31711b08",
   "metadata": {},
   "outputs": [],
   "source": [
    "puissance(2.0, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "adccc3e2",
   "metadata": {},
   "source": [
    "## Calcul de puissance rapide\n",
    "\n",
    "Pour calculer $x^n$ (avec $x$ flottant et $n$ entier naturel) en temps $\\Omicron(\\log_2(n))$, on remarque que:\n",
    "- si $n$ est pair, alors $x^n = (x^{\\frac{n}{2}})^2$\n",
    "- si $n$ est impair, alors $x^n = x \\cdot (x^{\\frac{n}{2}})^2$\n",
    "\n",
    "Ce principe permet de diviser $n$ par $2$ à chaque récursion, et donc à ne faire que $\\Omicron(\\log_2(n))$ appels récursifs.\n",
    "\n",
    "**NB:** attention cependant à ne pas calculer deux fois $x^{\\frac{n}{2}}$ pour atteindre cette complexité."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6ee1ae3a",
   "metadata": {},
   "outputs": [],
   "source": [
    "@trace\n",
    "def puissance_rapide(x: float, n: int) -> float:\n",
    "    assert n >= 0\n",
    "    if n == 0:\n",
    "        return 1.0\n",
    "    else:\n",
    "        p = puissance_rapide(x, n // 2)\n",
    "        if n % 2 == 0:   # n pair        \n",
    "            return p**2\n",
    "        else:            # n impair\n",
    "            return x * p**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1c7f29ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "puissance_rapide(2.0, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1cd83111",
   "metadata": {},
   "source": [
    "## Calcul du nombre de chiffres d'un entier positif ou nul\n",
    "\n",
    "Écrire une fonction récursive qui calcule le nombre de chiffres d'un entier `n` positif ou nul"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "91fb4f65",
   "metadata": {},
   "outputs": [],
   "source": [
    "@trace\n",
    "def nb_chiffres(n: int) -> int:\n",
    "    assert n >= 0\n",
    "    if n < 10:\n",
    "        return 1\n",
    "    else:\n",
    "        return 1 + nb_chiffres(n // 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9ece93cc",
   "metadata": {},
   "outputs": [],
   "source": [
    "nb_chiffres(3289273493)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52928fe7",
   "metadata": {},
   "source": [
    "## Somme des chiffres d'un entier positif ou nul\n",
    "\n",
    "Écrire une fonction récursive qui calcule la somme des chiffres d'un entier `n` positif ou nul"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1ce8ef0c",
   "metadata": {},
   "outputs": [],
   "source": [
    "@trace\n",
    "def somme_chiffres(n: int) -> int:\n",
    "    assert n >= 0\n",
    "    if n < 10:\n",
    "        return n\n",
    "    else:\n",
    "        return (n % 10) + somme_chiffres(n // 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2e377bb0",
   "metadata": {},
   "outputs": [],
   "source": [
    "somme_chiffres(123456789)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1e1d070",
   "metadata": {},
   "source": [
    "## Récursivité mutuelle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6b5b2533",
   "metadata": {},
   "outputs": [],
   "source": [
    "@trace\n",
    "def pair(n: int) -> bool:\n",
    "    assert n >= 0\n",
    "    if n == 0:\n",
    "        return True\n",
    "    else:\n",
    "        return impair(n-1)\n",
    "\n",
    "@trace\n",
    "def impair(n: int) -> bool:\n",
    "    assert n >= 0\n",
    "    if n == 0:\n",
    "        return False\n",
    "    else:\n",
    "        return pair(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6aac2559",
   "metadata": {},
   "outputs": [],
   "source": [
    "pair(15)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "defaultInterpreterPath: 3.14.8.final.0",
   "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.14.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}