{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/financieras/pyCourse/blob/main/jupyter/calisto1/0630_recursividad.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "9691958c",
      "metadata": {
        "id": "9691958c"
      },
      "source": [
        "# Funciones: recursividad"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "218be421",
      "metadata": {
        "id": "218be421"
      },
      "source": [
        "![recursividad](https://github.com/financieras/pyCourse/blob/main/jupyter/img/recursividad.png?raw=1)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "3e41dfba",
      "metadata": {
        "id": "3e41dfba"
      },
      "source": [
        "## Función recursiva sin return\n",
        "Una función recursiva se llama a sí misma, pero en algún momento se debe interrumpir."
      ]
    },
    {
      "cell_type": "markdown",
      "id": "2317b793",
      "metadata": {
        "id": "2317b793"
      },
      "source": [
        "### Método 1"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "74a17474",
      "metadata": {
        "id": "74a17474"
      },
      "outputs": [],
      "source": [
        "def cuenta_regresiva(n):                  # cuenta atrás (countdown) usando una función que se llama a sí misma\n",
        "    if n > 0:\n",
        "        print(n)\n",
        "        n -= 1\n",
        "        cuenta_regresiva(n)               # la función se llama a si misma despues de imprimir n y reducir el valor de n en 1\n",
        "    else:\n",
        "        print(\"Hasta la vista, Baby.\")\n",
        "    #print(\"Fin función\", n)              # si queremos ver cuándo termina cada una de las funciones\n",
        "\n",
        "cuenta_regresiva(5)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "bf42864f",
      "metadata": {
        "id": "bf42864f"
      },
      "source": [
        "### Método 2\n",
        "Se llama 'caso base' al momento en el que queremos que termite la recursividad."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "2a371eda",
      "metadata": {
        "id": "2a371eda"
      },
      "outputs": [],
      "source": [
        "def countdown(n):                  # cuenta atrás (countdown) usando una función que se llama a sí misma\n",
        "    if n == 0:                     # caso base\n",
        "        print(\"Despegando...\")\n",
        "    else:\n",
        "        print(n)\n",
        "        countdown(n-1)\n",
        "\n",
        "countdown(5)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "91a08ff5",
      "metadata": {
        "id": "91a08ff5"
      },
      "source": [
        "## Función recursiva con return: acumula  \n",
        "Dado un número entero n>1 sumar todos los números desde 1 hasta n.  \n",
        "Por ejemplo, para n=5 se obtendría la suma de 1+2+3+4+5 que es 15.  \n",
        "Compruebe que la suma de los números del 1 al 100 es igual a 5050.  \n",
        "[Midiendo el mundo](https://youtu.be/9JxnGx0RWso)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "3f06074f",
      "metadata": {
        "id": "3f06074f"
      },
      "source": [
        "### Cálculo del acumulado por iteración"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "55f9624d",
      "metadata": {
        "id": "55f9624d"
      },
      "outputs": [],
      "source": [
        "def sumando(n):\n",
        "    total = 0\n",
        "    for i in range(n+1):\n",
        "        total += i\n",
        "    return total\n",
        "\n",
        "print(sumando(5))"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "29f4d5a5",
      "metadata": {
        "id": "29f4d5a5"
      },
      "source": [
        "### Cálculo del acumulado por recursión"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "ec54c268",
      "metadata": {
        "id": "ec54c268"
      },
      "outputs": [],
      "source": [
        "def suma(n):\n",
        "    if n == 0:\n",
        "        return 0               # definimos el resultado para el caso base\n",
        "    else:\n",
        "        return n + suma(n-1)   # definimos el resultado para el resto de los casos\n",
        "\n",
        "print(suma(5))"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "58583adf",
      "metadata": {
        "id": "58583adf"
      },
      "source": [
        "`_` representa 'algo que aún no se'\n",
        "\n",
        "* 5 + `_`\n",
        "* 4 + `_`\n",
        "* 3 + `_`\n",
        "* 2 + `_`\n",
        "* 1 + `_`\n",
        "* 0 → al llegar a cero ya devuelve algo, devuelve cero\n",
        "\n",
        "Ahora se completa el ciclo hacia atrás, rellenando los huecos `_`\n",
        "\n",
        "* 5 + 10 → 15\n",
        "* 4 +  6 → 10\n",
        "* 3 +  3 → 6\n",
        "* 2 +  1 → 3\n",
        "* 1 +  0 → 1\n",
        "* 0 →  0   (ahora, empezamos a leer comenzando por el último)\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "b3c4c1a2",
      "metadata": {
        "id": "b3c4c1a2"
      },
      "source": [
        "## Factorial de un número"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "66a19562",
      "metadata": {
        "id": "66a19562"
      },
      "source": [
        "* El factorial de 5 es:\n",
        "$$5! = 5 * 4 * 3 * 2 * 1$$  \n",
        "* Por definición, el factorial de 0 es 1.\n",
        "$$0! = 1$$"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "39c2775a",
      "metadata": {
        "id": "39c2775a"
      },
      "source": [
        "### Función factorial importando la librería math"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "21ce742f",
      "metadata": {
        "id": "21ce742f"
      },
      "outputs": [],
      "source": [
        "from math import factorial\n",
        "factorial(5)                                   # pruebe a calcular el factorial de 1000"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "ff70c558",
      "metadata": {
        "id": "ff70c558"
      },
      "source": [
        "### Cálculo del factorial por iteración"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "b5be03a7",
      "metadata": {
        "id": "b5be03a7"
      },
      "outputs": [],
      "source": [
        "def factor(n):\n",
        "    f = 1                                        #por definición el factorial de cero es 1\n",
        "    for i in range(1, n+1):\n",
        "        f *= i\n",
        "    return f\n",
        "\n",
        "n = 5\n",
        "print(\"El producto de 5*4*3*2*1 es\", 5*4*3*2*1)\n",
        "print(\"El factorial de\", n, \"es\", factor(n))"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "eb913069",
      "metadata": {
        "id": "eb913069"
      },
      "source": [
        "### Cálculo del factorial por recursión"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "89cce801",
      "metadata": {
        "id": "89cce801"
      },
      "outputs": [],
      "source": [
        "def fac(n):\n",
        "    if n == 0:                # condición de parada\n",
        "        return 1              # caso base\n",
        "    else:\n",
        "        return n * fac(n-1)   # equivale a   else:n*=fac(n-1);return n\n",
        "\n",
        "n = 5\n",
        "print(f\"El factorial de {n} es {fac(n)}\")"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "d58b28e2",
      "metadata": {
        "id": "d58b28e2"
      },
      "source": [
        "## Imprimir una lista por recursividad\n",
        "Dada una lista imprimir sus elementos comenzando desde un índice dado."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "ab54700d",
      "metadata": {
        "id": "ab54700d"
      },
      "outputs": [],
      "source": [
        "def imprimir_lista(l, i):         # l es la lista e i es el índice por el que comenzar a imprimir\n",
        "    if i != len(l):\n",
        "        print(l[i])\n",
        "        imprimir_lista(l, i+1)    # al poner i+1 estamos comenzando el proceso, pero habiendo incrementado i en 1\n",
        "\n",
        "l  = [6, 7, 8, 9]\n",
        "imprimir_lista(l, 0)              # Estamos pidiendo comenzar por el índice 0"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "2b011d8d",
      "metadata": {
        "id": "2b011d8d"
      },
      "source": [
        "## Sucesión de Fibonacci  \n",
        "[Sucesión de Fibonacci programada en Python](https://altocodigo.blogspot.com/2018/07/sucesion-de-fibonacci-programada-en.html)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "689470d3",
      "metadata": {
        "id": "689470d3"
      },
      "source": [
        "### Fibonacci por iteraciones"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "437ef95e",
      "metadata": {
        "id": "437ef95e"
      },
      "outputs": [],
      "source": [
        "fibo=[0, 1]\n",
        "for i in range (17):\n",
        "  fibo.append(fibo[-1] + fibo[-2])\n",
        "print(fibo)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "59ad93db",
      "metadata": {
        "id": "59ad93db"
      },
      "source": [
        "### Fibonacci por recursión"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "0019f767",
      "metadata": {
        "id": "0019f767"
      },
      "outputs": [],
      "source": [
        "def fib(n):\n",
        "    if n <= 0: return 0\n",
        "    if n == 1: return 1\n",
        "    return fib(n-1) + fib(n-2)\n",
        "\n",
        "#print(fib(18))                      # 2584\n",
        "[fib(i) for i in range(19)]"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "13a5e01b",
      "metadata": {
        "id": "13a5e01b"
      },
      "source": [
        "Otra versión similar a la anterior con una línea menos."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "1b05bb1c",
      "metadata": {
        "id": "1b05bb1c"
      },
      "outputs": [],
      "source": [
        "def fib(n):                          # necesariamente debe ser n>=0\n",
        "    if n <= 1: return n              # si n=1 retorna 1. si n=0 retorna 0\n",
        "    return fib(n-1) + fib(n-2)\n",
        "\n",
        "[fib(i) for i in range(19)]"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "ccb9e498",
      "metadata": {
        "id": "ccb9e498"
      },
      "source": [
        "**Ejercicio**  \n",
        "Encuentre la suma de todos los términos pares en Fibonacci que no superen los cuatro millones."
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def fib(n):\n",
        "    if n <= 1: return n\n",
        "    return fib(n-1) + fib(n-2)\n",
        "\n",
        "if __name__ == \"__main__\":\n",
        "    n = valor = suma = 0\n",
        "    while True:\n",
        "        valor = fib(n)\n",
        "        if valor > 4_000_000:\n",
        "            break\n",
        "        suma += valor\n",
        "        print(f\"n={n:2}, fib({n:2d})={valor:7}, suma={suma:7}\")\n",
        "        n += 2   # comenzando en n=0 da los pares"
      ],
      "metadata": {
        "id": "hQTfSiDBwCwR"
      },
      "id": "hQTfSiDBwCwR",
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "id": "9f6a7e65",
      "metadata": {
        "id": "9f6a7e65"
      },
      "source": [
        "## Reverso de un string por recursión"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "46bdb631",
      "metadata": {
        "id": "46bdb631"
      },
      "outputs": [],
      "source": [
        "def reverso(cadena):\n",
        "    if len(cadena) == 0: return ''\n",
        "    return cadena[-1] + reverso(cadena[:-1])\n",
        "\n",
        "print(reverso('sogima'))"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "794906e0",
      "metadata": {
        "id": "794906e0"
      },
      "source": [
        "**Ejercicio del palíndromo**  \n",
        "* Detecte si una palabra es un palíndromo o no\n",
        "* Resuelva el caso con una función por iteraciones y por recursividad.\n",
        "* ¿Cuál de las dos versiones le resulta preferible?"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "d246b2e2",
      "metadata": {
        "id": "d246b2e2"
      },
      "source": [
        "## Ventajas de la recursión  \n",
        "- Al dividir el problema en partes más pequeña es más abordable.\n",
        "- Puede llegar a mostrarse un código más limpio y ordenado."
      ]
    },
    {
      "cell_type": "markdown",
      "id": "60ecb9b3",
      "metadata": {
        "id": "60ecb9b3"
      },
      "source": [
        "## Inconvenientes de la recursión  \n",
        "* La lógica es difícil de seguir.\n",
        "* En Python la llamada recursiva a una función ocupa una gran cantidad de memoria ya que permanece abierta cada una de las llamadas (cada una de las instancias).\n",
        "* Python establecen en 3000 en número límite de llamadas recursivas a una función, después de ello arroja un error.  \n",
        " *RecursionError: maximum recursion depth exceeded in comparison*  \n",
        "* Si la recursividad es demasiado profunda, puede quedarse sin espacio de pila, lo que se denomina desbordamiento de pila (**stack overflow**).\n",
        "* Otro inconveniente es que las subfunciones recursivas requieren mucho tiempo por lo que son ineficientes."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "b11332c1",
      "metadata": {
        "id": "b11332c1"
      },
      "outputs": [],
      "source": [
        "import sys\n",
        "sys.getrecursionlimit()"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "fe2c9b56",
      "metadata": {
        "id": "fe2c9b56"
      },
      "source": [
        "Ese límite se podría ampliar."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "0ac85eb3",
      "metadata": {
        "id": "0ac85eb3"
      },
      "outputs": [],
      "source": [
        "#import sys\n",
        "#sys.setrecursionlimit(5000)"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## ¿Cómo crear un stack overflow?\n",
        "Una forma sencilla de crear un desbordamiento de pila es crear una función que se llame a si misma.\n",
        "\n",
        "Se producirá un error del tipo:\n",
        "\n",
        "- RecursionError: maximum recursion depth exceeded"
      ],
      "metadata": {
        "id": "jOV6kkuX4cLd"
      },
      "id": "jOV6kkuX4cLd"
    },
    {
      "cell_type": "code",
      "source": [
        "def hola():\n",
        "    hola()\n",
        "\n",
        "hola()"
      ],
      "metadata": {
        "id": "BGbulLuC4fxb"
      },
      "id": "BGbulLuC4fxb",
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "id": "8edaae2d",
      "metadata": {
        "id": "8edaae2d"
      },
      "source": [
        "## Calcular el máximo"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "9c7da259",
      "metadata": {
        "id": "9c7da259"
      },
      "source": [
        "Ya existe una función en Python que calcula el máximo de varios números, pero vamos a crear nuestra propia función para calcular el máximo por iteración y por recursividad."
      ]
    },
    {
      "cell_type": "markdown",
      "id": "4ee0678d",
      "metadata": {
        "id": "4ee0678d"
      },
      "source": [
        "### Función max interna de Python"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "0d754e35",
      "metadata": {
        "id": "0d754e35"
      },
      "outputs": [],
      "source": [
        "max(3, 9, 6)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "a9240696",
      "metadata": {
        "id": "a9240696"
      },
      "source": [
        "### Función máximo creada por iteración"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "f94f1064",
      "metadata": {
        "id": "f94f1064"
      },
      "outputs": [],
      "source": [
        "def mimax(*numeros):                 #se pone * cuando el número de datos de entrada es indeterminado\n",
        "    maximo = numeros[0]\n",
        "    for numero in numeros:\n",
        "        if numero > maximo:\n",
        "            maximo = numero\n",
        "    return maximo\n",
        "\n",
        "print(mimax(3, 9, 6))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "f036169e",
      "metadata": {
        "id": "f036169e"
      },
      "outputs": [],
      "source": [
        "def mymax(numeros):                  # usando una lista no es necesario usar *\n",
        "    maximo = numeros[0]\n",
        "    for numero in numeros:\n",
        "        if numero > maximo:\n",
        "            maximo = numero\n",
        "    return maximo\n",
        "lista=[3, 9, 6]\n",
        "print(mymax(lista))"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "48fd5035",
      "metadata": {
        "id": "48fd5035"
      },
      "source": [
        "### Función máximo creada por recursión"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "9760eac9",
      "metadata": {
        "id": "9760eac9"
      },
      "source": [
        "#### Método 1 por recursión"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "e148f01e",
      "metadata": {
        "id": "e148f01e"
      },
      "outputs": [],
      "source": [
        "def maximo(l):\n",
        "    if len(l) == 1: return l[0]\n",
        "    else: return max(l[0], maximo(l[1:]))  #calcula el max entre el primer elemento de la lista y el resto de ella\n",
        "\n",
        "num=[3, 9, 6]\n",
        "maximo(num)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "df99ab4b",
      "metadata": {
        "id": "df99ab4b"
      },
      "source": [
        "Una variante del código anterior, ahora usando el final de la lista."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "abf017d1",
      "metadata": {
        "id": "abf017d1"
      },
      "outputs": [],
      "source": [
        "def maxi(l):\n",
        "    if len(l)==1: return l[0]\n",
        "    return max(l[-1], maxi(l[:-1]))  #calcula el max entre el último elemento de la lista y el resto de ella\n",
        "\n",
        "lista=[3, 9, 6]\n",
        "maxi(lista)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "5a9feb5f",
      "metadata": {
        "id": "5a9feb5f"
      },
      "source": [
        "#### Método 2 por recursión  \n",
        "Otro método, en este caso sin usar la función matemática max.  \n",
        "Se comparan el último y el primer elemento de la lista y se va dejando el mayor en la primera posición."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "02604db1",
      "metadata": {
        "id": "02604db1"
      },
      "outputs": [],
      "source": [
        "def maximo(li):                            # al final la lista li solo tendrá un elemento que será el máximo\n",
        "    if len(li) == 1: return li[0]          # caso base: el máximo habrá quedado en la primera posición de la lista\n",
        "    else:\n",
        "        li[-1] > li[0]                     # actúa si el último valor de la lista es mayor\n",
        "        li[-1], li[0] = li[0], li[-1]      # permutamos los valores, último y primero de la lista\n",
        "        li.pop()                           # eliminamos el último valor de la lista\n",
        "    return maximo(li)\n",
        "\n",
        "li=[3, 9, 6]\n",
        "maximo(li)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "a7025edd",
      "metadata": {
        "id": "a7025edd"
      },
      "source": [
        "#### Método 3 por recursión  \n",
        "Sin usar la función matemática max y sin ir eliminando el último elemento de la lista."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "175aceb8",
      "metadata": {
        "id": "175aceb8"
      },
      "outputs": [],
      "source": [
        "def maximiza(l):\n",
        "    if len(l) == 1:\n",
        "       return l[0]\n",
        "    else:\n",
        "       candidato = maximiza(l[1:])\n",
        "       m = l[0]\n",
        "       if candidato > m:\n",
        "            m = candidato\n",
        "       return m\n",
        "\n",
        "num=[3, 9, 6]                         # si la lista estuviera vacía daría error y necesitaríamos control de errores\n",
        "maximiza(num)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "b1840af8",
      "metadata": {
        "id": "b1840af8"
      },
      "source": [
        "## Máximo Común Divisor  \n",
        "[Máximo común divisor (MCD) en Python](https://altocodigo.blogspot.com/2021/01/maximo-comun-divisor-mcd-en-python.html)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "b91b5967",
      "metadata": {
        "id": "b91b5967"
      },
      "source": [
        "### MCD con la librería math.gcd"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "5cbfd6e4",
      "metadata": {
        "id": "5cbfd6e4"
      },
      "outputs": [],
      "source": [
        "from math import gcd\n",
        "gcd(300, 33880)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "53191a90",
      "metadata": {
        "id": "53191a90"
      },
      "source": [
        "El inconveniente de esta librería es que solo calcula el MCD de dos números.  \n",
        "Existe una propiedad del MCD que dice:  \n",
        "gcd(a,b,c) = gcd(gcd(a,b),c)  para 0≠a, b, c∈Z"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "e517bb15",
      "metadata": {
        "id": "e517bb15"
      },
      "source": [
        "### MCD por recursión"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "c704afb5",
      "metadata": {
        "id": "c704afb5"
      },
      "outputs": [],
      "source": [
        "from math import gcd\n",
        "\n",
        "def mcd(l):\n",
        "    if len(l)==2:\n",
        "        return gcd(l[0], l[1])\n",
        "    else:\n",
        "        return gcd(l[-1], mcd(l[:-1]))\n",
        "\n",
        "lista = [300, 33880, 70]\n",
        "mcd(lista)"
      ]
    }
  ],
  "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.8.8"
    },
    "colab": {
      "name": "0630_recursividad.ipynb",
      "provenance": [],
      "include_colab_link": true
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}