Baner principal del sitio

DICCIONARIO DE TÉRMINOS INFORMÁTICOS DEL TICUS



Selecciona una letra

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Búsca una palabra

palabra

¿Qué es Recursividad?

Definición de Recursividad:
Imagen de Recursividad
Imagen de Recursividad
1. Se puede definir como: El proceso de resolver un problema reduciéndolo a uno o más subproblemas que son idénticos en su estructura al problema original y más simples de resolver.

Una vez que se ha subdividido el problema original, se utiliza la misma técnica de descomposición para subdividir cada uno de estos subproblemas en otros que son menos complejos, hasta que los subproblemas llegan a ser tan simples que se pueden resolver sin realizar más subdivisiones, y la solución general del problema se obtiene juntando todos los componentes resueltos.

Se dice que un proceso es recursivo si forma parte de sí mismo, es decir, que se define en función de sí mismo. La recursión aparece en la vida diaria, en problemas matemáticos, en estructuras de datos y en muchos otros problemas. Es un proceso extremadamente potente, por lo que hay que saber cuándo y cómo aplicarla.

Existen 4 reglas fundamentales de la recursión, que tenemos que tener en cuenta a la hora de realizar nuestro algoritmo.

1. Caso Base: se debe tener siempre, al menos un caso base que pueda resolverse sin recursión.
2. Progreso: cualquiera llamada recursiva debe progresar hacia un caso base.
3. Puede creerlo: asuma siempre que toda llamada recursiva interna funciona correctamente.
4. Interes compuesto: nunca duplique el trabajo resolviendo la misma instancia de un problema, en llamadas recursivas separadas.



Ejemplo de la Recursividad Lineal.

Máximo común divisor entre a y b:


 def mcd( a, b):

 if( b==0):

 return a

 else:

 return mcd( b, a%b)




Ejemplo: Obtener el factorial de un número



def factorial(n):

if( n==1):

return 1

else:

return n * factorial(n-1)




Ejemplo: Obtener el n-ésimo valor de la serie de Fibonacci



def fibonacci(n):

if( n<=1):

return 1

else:

return fibonacci(n-1) + fibonacci(n-2)
Temas relacionados: Algoritmo, Algoritmo de búsqueda, Código fuente, Diagrama de flujo, Expresiones, JavaScript, Lenguajes de programación, Operadores, PHP, Programa, Programación Funcional, Programación Imperativa, Programación lógica, Programación orientada al evento, Programación Orientada al Objetos (POO), Pseudocódigo, UML.