Explicación del concepto de Recursividad usando Python y diferentes ejemplos de funciones

recursividad.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Z404UWgdzojq"
   },
   "source": [
    "# Recursividad\n",
    "### Autor Jorge Calvo\n",
    "\n",
    "La recursividad es una de las herramientas más potentes e importantes en Computación. El concepto no se limita solo al ambito de la programación si no que se encuentra presenta en la propia naturaleza.\n",
    "\n",
    "### Definición \n",
    "***Una función es recursiva cuando se define en términos de si misma, como por ejemplo.***\n",
    "\n",
    "La función **factorial**\n",
    "\n",
    "$f(x)=x!$\n",
    "\n",
    "$n!= n * n(n-1) * ..... * 3 * 2 * 1 $\n",
    "\n",
    "$5! = 5.4.3.2.1$\n",
    "\n",
    "### Esta función se puede expresar tambien como una función recursiva\n",
    "* $f(x) = x * f(x-1)!$ \n",
    "\n",
    "#### **Vamos a verlo en Python**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "#sin recursividad\n",
    "def factorial(n):\n",
    "    if n==0: return print(1)\n",
    "    for x in range (1,n):\n",
    "        n=n*x\n",
    "    return print(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "120\n"
     ]
    }
   ],
   "source": [
    "factorial(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "id": "g7oADcAUzahG"
   },
   "outputs": [],
   "source": [
    "#con recursividad\n",
    "def factorial_r(n): #Declaro una función llamada factorial\n",
    "  if (n==1) or (n==0): #Controlo los dos valores que siempre dan uno en un factorial, el 1 y el 0 \n",
    "    return 1 #Si esto se cumple siempre devuelve el valor 1\n",
    "  else: #Si es cualquier otro valor , retorno la función recursiva\n",
    "    return n*factorial(n-1) #Función recursiva"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "id": "HAEvbeqP3CzA"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "720\n"
     ]
    }
   ],
   "source": [
    "factorial(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Potencias\n",
    "Ene ste ejercicio vamos a trabajar con las potencias. \n",
    "\n",
    "* $a^n=\\prod^n_{i=1}a_i$\n",
    "* $a^n=a * a^{n-1}$\n",
    "\n",
    "Debemos realizar una función en Python a la cual le pase dos parametros (x,y), uno de ellos es la base y el otro el exponente. La función me debe devolver el resultado de esa potencia. \n",
    "\n",
    "#### **Vamos a verlo en Python**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "#sin recursividad\n",
    "def potencia(base,exp):\n",
    "  if exp==0:\n",
    "    return 1\n",
    "  else:\n",
    "    r=base\n",
    "    for x in range (1,exp):\n",
    "      r=base*r\n",
    "    return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "potencia(2,5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Con recursividad\n",
    "def potencia_r(base,exp):\n",
    "  if exp==0:\n",
    "    return 0\n",
    "  if exp==1:\n",
    "    return base\n",
    "  else: \n",
    "    return base * potencia_r(base,exp-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "potencia_r(2,5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Serie de Fibonnaci\n",
    "\n",
    "* Vamos a trabajar con la famosa serie de **Fibonacci**. Debéis recordar que la serie de Fibonacci es muy sencilla de aplicar. \n",
    "#### Se representa como: $f_n=f_{n-1}+f_{n-2}$. \n",
    "* Consiste en sumar en una sucesión de números que comienza con 0 y 1. Sumar los dos números anteriores para hallar el tercero. Es decir:\n",
    "\n",
    "* 0+1= 1\n",
    "* 1+1=2\n",
    "* 1+2=3\n",
    "* 2+3=5\n",
    "* 3+5=8\n",
    "\n",
    "Debemos realizar una función en Python a la cual le pase un único parametro (n), la posición en la serie de Fibonacci. La función me debe devolver el número en la posición **n**.\n",
    "\n",
    "#### **Vamos a verlo en Python**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Sin recursividad\n",
    "def fibonacci(n):\n",
    "  f=[0,1]\n",
    "  r=0\n",
    "  for x in range (0,n-1):\n",
    "    r=f[x]+f[x+1]    \n",
    "    f.append(r)\n",
    "  return print(f[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "144\n"
     ]
    }
   ],
   "source": [
    "fibonacci(12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Con recursividad\n",
    "def fibonacci_r(n):\n",
    "  if n==0:\n",
    "    return 0\n",
    "  if n==1:\n",
    "    return 1\n",
    "  else:\n",
    "    return fibonacci_r(n-1)+fibonacci_r(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "144"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fibonacci_r(12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "ZhxE6WUV4Fo6"
   },
   "source": [
    "# Las Torres de Hanoi\n",
    "\n",
    "Se conoce como un juego matemático inventado por el francés **Édouard Lucas** en 1883. Consiste en pasar **n** discos apilados y ordenados por tamaño de una estaca a otra, utilizando una estaca auxiliar si fuera necesario. \n",
    "#### ***Siguiendo unas simples reglas*** \n",
    "\n",
    "* Un disco de radio R nunca se ponga encima de otro de radio r (asumiendo que R>r)\n",
    "\n",
    "* Solo es posible mover un disco a la vez y siempre el disco en el tope de la pila\n",
    "\n",
    "<img src=\"https://www.compartirpalabramaestra.org/sites/default/files/images/compartirsaberes/matematicas/torres-de-hanoi.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "yF4adw3m5qna"
   },
   "source": [
    "### ¿Cual es el menor número de movimientos para pasar 3 discos?\n",
    "#### Intentalo en:\n",
    "\n",
    "https://www.geogebra.org/m/NqyWJVra\n",
    "\n",
    "#### Hay un algoritmo que me resuelva el juego para **n** discos\n",
    "#### ¿Que ocurre cuando el número de discos es muy alto?\n",
    "#### ¿Puedo saber el número minimo de movimientos?\n",
    "#### ¿Cuanto puedo tardar?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "EyAviob4Hthg"
   },
   "source": [
    "# Vamos a resolver con Recursividad y Python\n",
    "Lo primero que debemos entender es que para resolver el juego hay un patrón que debemos reconocer:\n",
    "\n",
    "Llamemos a las Torres\n",
    "* A (origen)\n",
    "* B (destino)\n",
    "* Aux (auxiliar)\n",
    "\n",
    "Llamemos a los discos\n",
    "* De 1 a n, siendo **n** el disco más grande  \n",
    "\n",
    "#### ¿Algoritmo? ¿Patrón?\n",
    "\n",
    "1A ==> 1C<br>\n",
    "2A ==> 2B<br>\n",
    "1C ==> 1B<br>\n",
    "\n",
    "3A ==> 3C<br>\n",
    "\n",
    "1B ==> 1A<br>\n",
    "2B ==> 2C<br>\n",
    "1A ==> 1C<br>\n",
    "\n",
    "#### **Vamos a verlo en Python**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "id": "B_HchOu53KdJ"
   },
   "outputs": [],
   "source": [
    "#Creamos una función en Python para el resolver el juego de Las Torres de Hanoi con cualquier número de discos\r\n",
    "def hanoi(disco,TorreOrigen,TorreDestino,TorreAuxiliar):\r\n",
    "  if disco==1:\r\n",
    "    print(\"Pasar disco de {} a {}\".format(TorreOrigen,TorreDestino))\r\n",
    "  else:\r\n",
    "    hanoi(disco-1,TorreOrigen,TorreAuxiliar,TorreDestino)\r\n",
    "    print(\"Pasar disco de {} a {}\".format(TorreOrigen,TorreDestino))\r\n",
    "    hanoi(disco-1,TorreAuxiliar,TorreDestino,TorreOrigen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "xo2PzmE9lGEg",
    "outputId": "69e2bcba-faf0-4e6b-e7e3-5eca028c2128"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Pasar disco de A a C\n",
      "Pasar disco de A a B\n",
      "Pasar disco de C a B\n",
      "Pasar disco de A a C\n",
      "Pasar disco de B a A\n",
      "Pasar disco de B a C\n",
      "Pasar disco de A a C\n"
     ]
    }
   ],
   "source": [
    "hanoi(3,\"A\",\"C\",\"B\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "DHrl__Q-lIoI"
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Recursividad Torres de Hanoi.ipynb",
   "provenance": []
  },
  "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}