Last active
January 14, 2021 13:11
-
-
Save jmcalvomartin/7a8b442f28f8da990287e27c4d54f13e to your computer and use it in GitHub Desktop.
Explicación del concepto de Recursividad usando Python y diferentes ejemplos de funciones
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"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