Recursividad

ESTRUCTURAS DE DATOS

UNIDAD 2 RECURSIVIDAD
Un proceso es recursivo, si está definido total o parcialmente en términos de sí mismo. La
utilización de la recursividad es apropiada cuando elproblema a resolver o los datos a tratar
han sido definidos de forma recursiva, aunque esto no garantiza que esta sea la mejor forma
de resolverlo.
La recursión es una alternativa a la iteración. Unproceso iterativo es aquel que requiere de la
expresión explicita de cierta acción.
De esta forma para calcular por ejemplo, el factorial de un número, se puede utilizar un
proceso iterativo o unorecursivo.
PROCED I MI EN TOS RECUR S I V OS

Los tipos de procesos recursivos son los siguientes:
a) Recursividad Simple o directa: Es aquella en cuya definición solo aparece una llamada
recursiva.Se puede transformar con facilidad en algoritmo iterativo.
b) Recursividad Múltiple: Se da cuando hay más de una llamada dentro del cuerpo de una
función o método, resulta un poco más difíciltransformar a un algoritmo en iterativo.
Por ejemplo:
int cuenta(int m)
{
if (m==1) return 1;
return (cuenta(m-10)+cuenta(m-2));
}
c) Recursividad Anidada: Es aquella en donde en alguno de losargumentos de la llamada
recursiva hay una nueva llamada así misma. Por ejemplo :
public int ack (int n, int m)
{
if(n==0) return(m+1)
else if(m==0)return(ack(n-1,1));
return(ack(n-1,ack(n,m-1)));
}d) Recursividad Cruzada o indirecta: Son algoritmos donde una función o método
provoca una llamada así mismo de forma indirecta a través de otras funciones o
métodos. Por ejemplo:
int par (intnump)
{
if(nump==0)return 1;
return (impar(nump-1));
}

1

ESTRUCTURAS DE DATOS

int impar (int numi)
{
if(numi==0)return 0;
return(par(numi-1));
}
M ECAN I CA D E RECURS I O N

Unalgoritmo recursivo se debe distinguir por dos elementos:
a) El caso base, trivial o de fin de recursión: Es un caso donde el problema puede
resolverse sin tener que hacer uso de una nueva llamada así...