Diferencia entre revisiones de «Recursividad»
(Página creada con ''''{{Definición|Nombre=Recursividad|imagen=recu.jpg}}'''<br> <div align="justify"> En el área de la programación de aplicaciones los programadores pueden enfrentarse a ...') (Etiqueta: Artículo sin Fuentes o Bibliografía o Referencias o Enlaces externos) |
m (Texto reemplazado: «<div align="justify">» por «») |
||
| (No se muestran 11 ediciones intermedias de otro usuario) | |||
| Línea 1: | Línea 1: | ||
'''{{Definición|Nombre=Recursividad|imagen=recu.jpg}}'''<br> | '''{{Definición|Nombre=Recursividad|imagen=recu.jpg}}'''<br> | ||
| − | + | ||
En el área de la [[programación]] de aplicaciones los programadores pueden enfrentarse a problemas de cualquier complejidad y buscar la solución más eficiente para cada uno de ellos. Algunos de estos problemas, siempre y cuando puedan ser definidos en función de su tamaño, es decir, si es posible llegar a su solución a través de una secuencia finita de pasos, pueden ser resueltos mediante la división del problema en subproblemas más pequeños y repitiendo esta acción para cada uno de los subproblemas que van surgiendo hasta llegar a problemas cuya solución es conocida o fácil de encontrar. | En el área de la [[programación]] de aplicaciones los programadores pueden enfrentarse a problemas de cualquier complejidad y buscar la solución más eficiente para cada uno de ellos. Algunos de estos problemas, siempre y cuando puedan ser definidos en función de su tamaño, es decir, si es posible llegar a su solución a través de una secuencia finita de pasos, pueden ser resueltos mediante la división del problema en subproblemas más pequeños y repitiendo esta acción para cada uno de los subproblemas que van surgiendo hasta llegar a problemas cuya solución es conocida o fácil de encontrar. | ||
| − | == | + | ==Definición== |
La [[recursividad]], también llamada recursión o recurrencia, es la forma en la cual se especifica un proceso basado en su propia definición. O sea, si se tiene un problema de tamaño N, este puede ser dividido en instancias más pequeñas que N del mismo problema y conociendo la solución de las instancias más simples, se puede aplicar inducción a partir de estas asumiendo que quedan resueltas. | La [[recursividad]], también llamada recursión o recurrencia, es la forma en la cual se especifica un proceso basado en su propia definición. O sea, si se tiene un problema de tamaño N, este puede ser dividido en instancias más pequeñas que N del mismo problema y conociendo la solución de las instancias más simples, se puede aplicar inducción a partir de estas asumiendo que quedan resueltas. | ||
| − | == | + | ==Condiciones necesarias== |
Para dar solución a un problema a partir del empleo de la recursividad, es necesario asegurar que cada llamada recursiva debe estar definida sobre un problema menos complejo que el que dio lugar a la llamada, y que debe existir al menos un caso base al que se garantice la llegada del problema en un momento determinado. Si no se cumpliera esta condición se generaría una secuencia infinita de llamadas y el algoritmo que intenta dar solución al problema no terminaría nunca. | Para dar solución a un problema a partir del empleo de la recursividad, es necesario asegurar que cada llamada recursiva debe estar definida sobre un problema menos complejo que el que dio lugar a la llamada, y que debe existir al menos un caso base al que se garantice la llegada del problema en un momento determinado. Si no se cumpliera esta condición se generaría una secuencia infinita de llamadas y el algoritmo que intenta dar solución al problema no terminaría nunca. | ||
| − | == | + | ==Ejemplos de recursividad== |
Las siglas que identifican al proyecto [[GNU]], creado por [[Richard Stallman]] son un ejemplo de recursividad, ya que su significado es GNU is not Unix, (en español GNU no es Unix), donde la G realizaría una nueva llamada a la sigla. | Las siglas que identifican al proyecto [[GNU]], creado por [[Richard Stallman]] son un ejemplo de recursividad, ya que su significado es GNU is not Unix, (en español GNU no es Unix), donde la G realizaría una nueva llamada a la sigla. | ||
| − | En la programación existen problemas conocidos que se pueden resolver | + | En la programación existen problemas conocidos que se pueden resolver empleando la recursividad, como son la Sucesión de Fibonacci, el problema de las 8 reinas, así como el cálculo del factorial y la potencia de un número. |
| − | == | + | ==Problemas resueltos de forma recursiva== |
| − | === | + | ===Producto de dos números=== |
| − | Un ejemplo de solución a un problema de forma recursiva sería | + | Un ejemplo de solución a un problema de forma recursiva sería calcular el producto de dos números de forma recurrente sin emplear el operador de multiplicación. Tomaremos como ejemplo la multiplicación de 3 y 4. Como caso base se conoce que el resultado de multiplicar cualquier número por 1 será el mismo número. |
3 * 4 se puede descomponer en 3 + 3 * 3 | 3 * 4 se puede descomponer en 3 + 3 * 3 | ||
Del mismo modo 3 * 3 se puede descomponer en 3 + 3 * 2 | Del mismo modo 3 * 3 se puede descomponer en 3 + 3 * 2 | ||
Y así sucesivamente | Y así sucesivamente | ||
| − | La figura | + | La figura muestra la secuencia de pasos completa que da solución al problema. |
| + | [[Imagen:multrec.jpg|thumb|center|]] | ||
| − | === | + | ===Torres de Hanoi=== |
Otro ejemplo es el problema de las Torres de Hanoi. El problema es el siguiente: | Otro ejemplo es el problema de las Torres de Hanoi. El problema es el siguiente: | ||
Se tiene tres postes: A, B y C. En el poste A se coloca una cantidad determinada de discos de diámetro diferente, de modo que un disco de diámetro menor siempre queda sobre uno de diámetro mayor. El objetivo es mover los discos al poste C usando el poste B como auxiliar. Sólo puede moverse el disco superior de cualquier poste a otro poste, y un disco mayor no puede estar en ningún momento sobre uno menor. | Se tiene tres postes: A, B y C. En el poste A se coloca una cantidad determinada de discos de diámetro diferente, de modo que un disco de diámetro menor siempre queda sobre uno de diámetro mayor. El objetivo es mover los discos al poste C usando el poste B como auxiliar. Sólo puede moverse el disco superior de cualquier poste a otro poste, y un disco mayor no puede estar en ningún momento sobre uno menor. | ||
| Línea 30: | Línea 31: | ||
Como se puede observar este problema no está planteado en términos recursivos, sin embargo se puede buscar una forma recursiva de dar solución al mismo. | Como se puede observar este problema no está planteado en términos recursivos, sin embargo se puede buscar una forma recursiva de dar solución al mismo. | ||
| − | La solución al problema de mover los n discos puede existir a partir de encontrar la solución al movimiento de n – 1 discos, pues al restar sucesivamente n – 1 llegaremos al caso base, mover un disco, cuya solución sería realizar el movimiento del disco de la torre A a la C, como se observa en la figura | + | La solución al problema de mover los n discos puede existir a partir de encontrar la solución al movimiento de n – 1 discos, pues al restar sucesivamente n – 1 llegaremos al caso base, mover un disco, cuya solución sería realizar el movimiento del disco de la torre A a la C, como se observa en la figura. |
| + | [[Imagen:Hanoi_um.png|thumb|center|]] | ||
| + | Si se deseara mover dos discos desde la posición inicial a la final los movimientos serían los que se muestran en la imagen. | ||
| + | [[Imagen:Hanoi_dm.png|thumb|center|]] | ||
| − | + | Conociendo la solución para el movimiento de dos discos, es posible buscar la solución para tres. De la misma forma en que se realizó el movimiento de dos discos desde A hasta C utilizando B como auxiliar, podemos desplazar estos dos discos de C hacia B empleando como auxiliar a A. | |
| + | [[Imagen:Hanoi_tm.png|thumb|center|]] | ||
| − | + | En este punto tendríamos los dos discos de menor tamaño en B y el mayor en A, el siguiente paso sería mover un disco de A a C como se hizo en el caso base y a continuación mover los discos restantes de B a C usando la torre A como auxiliar. | |
Siguiendo estas reglas, se puede hallar la solución al problema de n discos, conociendo la solución para n – 1. | Siguiendo estas reglas, se puede hallar la solución al problema de n discos, conociendo la solución para n – 1. | ||
En términos generales, la solución sería la siguiente: | En términos generales, la solución sería la siguiente: | ||
| − | - Si n es 1 mover el disco de A a C y terminar. | + | |
| − | - Si n es mayor que 1 entonces: | + | - Si n es 1 mover el disco de A a C y terminar. |
| − | - Mover el disco superior desde A hasta B n – 1 veces utilizando | + | - Si n es mayor que 1 entonces: |
| + | - Mover el disco superior desde A hasta B n – 1 veces utilizando C como auxiliar. | ||
- Mover el disco restante desde A hasta C. | - Mover el disco restante desde A hasta C. | ||
- Mover los n – 1 discos desde B hasta C empleando A como auxiliar. | - Mover los n – 1 discos desde B hasta C empleando A como auxiliar. | ||
| Línea 48: | Línea 54: | ||
Como se ha podido comprobar, la recursividad es una técnica que puede ayudar a encontrar soluciones a problemas cuya solución de manera iterativa resulta bastante engorrosa. El estudio de la misma resulta de gran ayuda para los programadores a la hora de dar respuesta a diversos problemas. </div> | Como se ha podido comprobar, la recursividad es una técnica que puede ayudar a encontrar soluciones a problemas cuya solución de manera iterativa resulta bastante engorrosa. El estudio de la misma resulta de gran ayuda para los programadores a la hora de dar respuesta a diversos problemas. </div> | ||
| − | == | + | ==Fuentes== |
http://es.wikipedia.org/wiki/Algoritmo_recursivo | http://es.wikipedia.org/wiki/Algoritmo_recursivo | ||
| + | |||
http://es.wikipedia.org/wiki/Recursi%C3%B3n | http://es.wikipedia.org/wiki/Recursi%C3%B3n | ||
| + | |||
Chávez Agüero, Abel Ing. Ciencias Informáticas | Chávez Agüero, Abel Ing. Ciencias Informáticas | ||
[[Category:Software]] | [[Category:Software]] | ||
última versión al 17:43 12 jul 2019
| ||||
En el área de la programación de aplicaciones los programadores pueden enfrentarse a problemas de cualquier complejidad y buscar la solución más eficiente para cada uno de ellos. Algunos de estos problemas, siempre y cuando puedan ser definidos en función de su tamaño, es decir, si es posible llegar a su solución a través de una secuencia finita de pasos, pueden ser resueltos mediante la división del problema en subproblemas más pequeños y repitiendo esta acción para cada uno de los subproblemas que van surgiendo hasta llegar a problemas cuya solución es conocida o fácil de encontrar.
Sumario
Definición
La recursividad, también llamada recursión o recurrencia, es la forma en la cual se especifica un proceso basado en su propia definición. O sea, si se tiene un problema de tamaño N, este puede ser dividido en instancias más pequeñas que N del mismo problema y conociendo la solución de las instancias más simples, se puede aplicar inducción a partir de estas asumiendo que quedan resueltas.
Condiciones necesarias
Para dar solución a un problema a partir del empleo de la recursividad, es necesario asegurar que cada llamada recursiva debe estar definida sobre un problema menos complejo que el que dio lugar a la llamada, y que debe existir al menos un caso base al que se garantice la llegada del problema en un momento determinado. Si no se cumpliera esta condición se generaría una secuencia infinita de llamadas y el algoritmo que intenta dar solución al problema no terminaría nunca.
Ejemplos de recursividad
Las siglas que identifican al proyecto GNU, creado por Richard Stallman son un ejemplo de recursividad, ya que su significado es GNU is not Unix, (en español GNU no es Unix), donde la G realizaría una nueva llamada a la sigla. En la programación existen problemas conocidos que se pueden resolver empleando la recursividad, como son la Sucesión de Fibonacci, el problema de las 8 reinas, así como el cálculo del factorial y la potencia de un número.
Problemas resueltos de forma recursiva
Producto de dos números
Un ejemplo de solución a un problema de forma recursiva sería calcular el producto de dos números de forma recurrente sin emplear el operador de multiplicación. Tomaremos como ejemplo la multiplicación de 3 y 4. Como caso base se conoce que el resultado de multiplicar cualquier número por 1 será el mismo número.
3 * 4 se puede descomponer en 3 + 3 * 3 Del mismo modo 3 * 3 se puede descomponer en 3 + 3 * 2 Y así sucesivamente La figura muestra la secuencia de pasos completa que da solución al problema.
Torres de Hanoi
Otro ejemplo es el problema de las Torres de Hanoi. El problema es el siguiente: Se tiene tres postes: A, B y C. En el poste A se coloca una cantidad determinada de discos de diámetro diferente, de modo que un disco de diámetro menor siempre queda sobre uno de diámetro mayor. El objetivo es mover los discos al poste C usando el poste B como auxiliar. Sólo puede moverse el disco superior de cualquier poste a otro poste, y un disco mayor no puede estar en ningún momento sobre uno menor.
Como se puede observar este problema no está planteado en términos recursivos, sin embargo se puede buscar una forma recursiva de dar solución al mismo.
La solución al problema de mover los n discos puede existir a partir de encontrar la solución al movimiento de n – 1 discos, pues al restar sucesivamente n – 1 llegaremos al caso base, mover un disco, cuya solución sería realizar el movimiento del disco de la torre A a la C, como se observa en la figura.
Si se deseara mover dos discos desde la posición inicial a la final los movimientos serían los que se muestran en la imagen.
Conociendo la solución para el movimiento de dos discos, es posible buscar la solución para tres. De la misma forma en que se realizó el movimiento de dos discos desde A hasta C utilizando B como auxiliar, podemos desplazar estos dos discos de C hacia B empleando como auxiliar a A.
En este punto tendríamos los dos discos de menor tamaño en B y el mayor en A, el siguiente paso sería mover un disco de A a C como se hizo en el caso base y a continuación mover los discos restantes de B a C usando la torre A como auxiliar.
Siguiendo estas reglas, se puede hallar la solución al problema de n discos, conociendo la solución para n – 1.
En términos generales, la solución sería la siguiente:
- Si n es 1 mover el disco de A a C y terminar. - Si n es mayor que 1 entonces: - Mover el disco superior desde A hasta B n – 1 veces utilizando C como auxiliar. - Mover el disco restante desde A hasta C. - Mover los n – 1 discos desde B hasta C empleando A como auxiliar.
Como se ha podido comprobar, la recursividad es una técnica que puede ayudar a encontrar soluciones a problemas cuya solución de manera iterativa resulta bastante engorrosa. El estudio de la misma resulta de gran ayuda para los programadores a la hora de dar respuesta a diversos problemas.
Fuentes
http://es.wikipedia.org/wiki/Algoritmo_recursivo
http://es.wikipedia.org/wiki/Recursi%C3%B3n
Chávez Agüero, Abel Ing. Ciencias Informáticas
