11-Funciones Recursivas.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "tc83rpEd-TqT"
   },
   "source": [
    "# Funciones recursivas \n",
    "\n",
    "\n",
    "En 1952 Stephen Kleene definió formalmente que una ``función parcial recursiva'' de enteros no negativos es cualquier función $f$ definida por un sistema no contradictorio de ecuaciones de las cuales las partes derechas e izquierdas están compuestas a partir de:\n",
    "\n",
    "\n",
    "1. Símbolos funcionales (por ejemplo, $f$, $g$, $h$, etc.),\n",
    "\n",
    "2. Variables para enteros no negativos (por ejemplo, $x$, $y$, $z$, etc.),\n",
    "\n",
    "3. La constante 0, y\n",
    "\n",
    "4. La función primitiva sucesor $s(x) = x + 1$.\n",
    "\n",
    "El siguiente es un sistema que define la función parcial recursiva $f(x,y)$ que permite computar el producto de $x$ con $y$.\n",
    "\\begin{align*}\n",
    "f(x,0) &= 0 \\\\\t\n",
    "f\\big(x,s(y)\\big) &= g\\big(f(x,y),x\\big) \\\\\n",
    "g(x,0) &= x \\\\\t\n",
    "g\\big(x,s(y)\\big) &= s\\big(g(x,y)\\big) \n",
    "\\end{align*}\n",
    "\n",
    "## Definición débil de función recursiva\n",
    "\n",
    "Una función $f:A\\to B$ se dice recursiva si y sólo si $f$ está definida por casos (mediante un predicado sobre los argumentos), en donde al menos uno de los casos se define usando la misma función $f$ y los argumentos, y al menos uno de los otros casos se define usando solamente los argumentos sin involucrar la función $f$. \n",
    "\n",
    "Mediante el uso de funciones recursivas se puede solucionar cualquier problema que es potencialmente solucionable haciendo uso de un computador. \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "E4kKIhghB2Dq"
   },
   "source": [
    "## Potencia de un número\n",
    "\n",
    "En este ejemplo se definirá una función recursiva que permita hallar un número real elevado a un número natural. Para expresar una función que calculé esta operación, en primera instancia se construye la expresión $potencia: \\mathbb{R} \\times \\mathbb{N} \\to \\mathbb{R}$ que define la función que tiene como entrada un número real que representa la base y un número natural que indica el exponente, y como salida se obtendrá un número real que será la potencia. Por facilidad, aquí se asumirá que $0^0 = 1$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 71
    },
    "id": "8IAaDFx4CBRi",
    "outputId": "b12c9651-3474-4d7f-add5-e83a03f4d6a2"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "digite la base: 2\n",
      "digite el exponente: 5\n",
      "2.0 ^ 5 = 32.0\n"
     ]
    }
   ],
   "source": [
    "def potencia(b, n):\n",
    "  if n == 0:\n",
    "    return 1\n",
    "  else:\n",
    "    return b*potencia(b, n-1)\n",
    "  \n",
    "  \n",
    "base = float(input('digite la base: '))\n",
    "exp = int(input('digite el exponente: '))\n",
    "print(base, '^', exp, '=', potencia(base, exp))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Z__jdJ9ZNw1g"
   },
   "source": [
    "## Pago Interés Compuesto mes vencido\n",
    "\n",
    "Supónga que solicita un préstamo de $1.000.000$ durante un año, el prestamista cobra un interés del $5\\%$ mensual mediante la modalidad de interes compuesto mes vencido. ¿Cuál es el total del dinero que debe pagar cuando ha transcurrido el año por el cual solicitó el prestamo?. (muestre el valor a pagar con dos cifras decimales).\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 88
    },
    "id": "bG-tbvECOBHu",
    "outputId": "76606ac0-2041-4de4-9f5c-83656acd8be7"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "m? = 1000000\n",
      "i? = 0.05\n",
      "n? = 12\n",
      "1795856.32602\n"
     ]
    }
   ],
   "source": [
    "def pago(m, i, n):\n",
    "  if n == 0:\n",
    "    return m\n",
    "  else:\n",
    "    return pago(m, i, n-1)*(1+i)\n",
    "  \n",
    "def main():\n",
    "  m = float(input('m? = '))\n",
    "  i = float(input('i? = '))\n",
    "  n = int(input('n? = '))\n",
    "  print(round(pago(m , i, n), 5))\n",
    " \n",
    "main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "eb6TAgT1CVIF"
   },
   "source": [
    "## Número de listas de los elementos de un conjunto\n",
    "\n",
    "Suponga que selecciona cuatro cartas distintas de una baraja de poker, que se van a representar por los símbolos:\n",
    "\n",
    "![texto alternativo](https://cdn.pixabay.com/photo/2019/08/22/13/34/card-4423526_960_720.jpg)\n",
    "\n",
    "\n",
    "¿De cuántas formas distintas se pueden organizar las cartas?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 53
    },
    "id": "PLAbUr9-DmuV",
    "outputId": "48595e85-1cfe-4084-f1b8-e66ef2ab09b0"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n? =4\n",
      "24\n"
     ]
    }
   ],
   "source": [
    "def fact(n):\n",
    "  if n == 0:\n",
    "    return 1\n",
    "  else:\n",
    "    return n*fact(n-1)\n",
    "  \n",
    "  \n",
    "n = int(input('n? ='))\n",
    "print(fact(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "onyLBBDzQONl"
   },
   "source": [
    "## Conteo de Subconjuntos\n",
    "\n",
    "Los Simpsons van a un parque de diversiones y quieren subir a la montaña rusa, por lo que sólo pueden subir Homero, Marge, Bart y Lisa, y en dicha montaña rusa cada vagón sólo dispone de dos puestos. ¿De cuantas formas se pueden formar parejas de la familia Simpson para que suban al vagón de la montaña rusa?."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 71
    },
    "id": "T_bclYFuQWUP",
    "outputId": "86634b97-43e8-4c88-f7d1-ee55571169ec"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n?4\n",
      "k?2\n",
      "C(n,k)=6\n"
     ]
    }
   ],
   "source": [
    "def C(n, k):\n",
    "  if k > n:\n",
    "    return 0\n",
    "  elif k == 0 or n == k:\n",
    "    return 1\n",
    "  else:\n",
    "    return C(n-1, k-1) + C(n-1, k)\n",
    "  \n",
    "def main():\n",
    "  n = int(input(\"n?\"))\n",
    "  k = int(input(\"k?\"))\n",
    "  print('C(n,k)=' + str(C(n,k)))\n",
    "\n",
    "main()\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "FtC_daDwQD62"
   },
   "source": [
    "## Los conejos de Fibonnacci\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 53
    },
    "id": "E4nVzZTfQNMK",
    "outputId": "d18bbf8d-9fb7-4543-d3f0-86aec0edd903"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n? =14\n",
      "Fibonnacci(n) = 377\n"
     ]
    }
   ],
   "source": [
    "def fibo(n):\n",
    "  if n == 0:\n",
    "    return 0\n",
    "  elif n == 1:\n",
    "    return 1\n",
    "  return fibo(n-1) + fibo(n-2)\n",
    "\n",
    "\n",
    "def main():\n",
    "  number = int(input('n? ='))\n",
    "  print(\"Fibonnacci(n) = \" + str(fibo(number)))\n",
    "  \n",
    "main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "gCW3qS60TbOs"
   },
   "source": [
    "## Saber si un número es primo o no\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 53
    },
    "id": "B6DJuj-tTsmn",
    "outputId": "3a9fd58c-10fb-47c5-b6a4-5f7f1e56c3d9"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n?14\n",
      "is prime:False\n"
     ]
    }
   ],
   "source": [
    "from math import sqrt\n",
    "\n",
    "def multiplo(n, d):\n",
    "  if and n % d == 0:\n",
    "    return True\n",
    "  elif d > sqrt(n):\n",
    "    return False\n",
    "  else:\n",
    "    return multiplo(n, d+1)\n",
    "\n",
    "def es_primo(num):\n",
    "  if n == 2:\n",
    "    return true\n",
    "  else:\n",
    "    return not multiplo(num, 2)\n",
    "\n",
    "def main():\n",
    "  num = int(input('n?'))\n",
    "  print('is prime:' + str(es_primo(num)))\n",
    "  \n",
    "main()\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "1oToFUXtcwwI"
   },
   "source": [
    "## Euclides\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 71
    },
    "id": "K4z9_2U1c5Hi",
    "outputId": "51f3a811-e524-484d-9154-6c48300c2139"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "p?18\n",
      "q?27\n",
      "mcd(p,q)=9\n"
     ]
    }
   ],
   "source": [
    "def mcd_recur(p, q):\n",
    "  if q == 0:\n",
    "    return p\n",
    "  return mcd_recur(q, p % q)\n",
    "\n",
    "\n",
    "def mcd(p, q):\n",
    "  if p > q:\n",
    "    return mcd_recur(p, q)\n",
    "  else:\n",
    "    return mcd_recur(q, p)\n",
    "\n",
    "def main():\n",
    "  p = int(input('p?'))\n",
    "  q = int(input('q?'))\n",
    "  print('mcd(p,q)='+str(mcd(p,q)))\n",
    "\n",
    "main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "id": "a53CXOWNgTIs",
    "outputId": "bcbd61ba-df31-4c24-f79b-28ca4b3a54e1"
   },
   "source": [
    "# Referencias \n",
    "\n",
    "Gomez, J, Rodriguez A y Cubides C. La ciencia de Programar. Universidad Nacional de Colombia."
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [
    "62ab8kI8rkZk"
   ],
   "name": "Python Notebook Curso Doctorado Parte I",
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}