Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Explicación del concepto de Recursividad usando Python y diferentes ejemplos de funciones
{
"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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment