Diferencia entre revisiones de «Recursión»
Contenido eliminado Contenido añadido
m Revertidos los cambios de 88.23.156.194 a la última edición de AVBOT |
|||
Línea 49:
= 6
== Algoritmo recursivo ==
{{AP|Algoritmo recursivo}}
Un método usual de simplificación de un problema complejo es la división de este en subproblemas del mismo tipo. Esta técnica de [[programación]] se conoce como [[divide y vencerás]] y es el núcleo en el diseño de numerosos algoritmos de gran importancia, así como también es parte fundamental de la [[programación dinámica]].
El ejemplo del cálculo recursivo del factorial de un número llevado al campo de la [[programación]], en este ejemplo [[C++]]:
int factorial (int x)
{
if (x < 2) return 1; // Caso base: Cuando X < 2 devolvemos 1 puesto que 1! = 1
return x*factorial(x - 1); // Si X >= 2 devolvemos el producto de 'X' por el factorial de 'X'-1
}
El seguimiento de la recursividad programada es casi exactamente igual al ejemplo antes dado, para intentar ayudar a que se entienda mejor se ha acompañado con muchas explicaciones y con colores que diferencia los distintos sub-procesos de la recursividad.
<font color="#0000FF">'''X = 3'''</font> //Queremos 3!, por lo tanto X inicial es 3
<font color="#0000FF">'''X >= 2 -> return 3*factorial(2);'''</font>
<font color="#B22222">'''X = 2'''</font> //Ahora estamos solicitando el factorial de 2
<font color="#B22222">'''X >= 2 -> return 2*factorial(1);'''</font>
<font color="#FF2700">'''X = 1'''</font> // Ahora estamos solicitando el factorial de 1
<font color="#FF2700">'''X < 2 -> return 1;'''</font>
[En este punto tenemos el factorial de 1 por lo que volvemos marcha atrás resolviendo todos los resultados]
<font color="#B22222">'''return 2'''</font> [es decir: return 2*1 = return 2*factorial(1)]
<font color="#0000FF">'''return 6'''</font> [es decir: return 3*2 = return 3*factorial(2)*factorial(1)] // El resultado devuelto es 6
== Ejemplos de recurrencias ==
| |||