El concepto de recursividad va ligado al de repetición. Son recursivos aquellos algoritmos que, estando encapsulados dentro de una función, son llamados desde ella misma una y otra vez, en contraposición a los algoritmos iterativos, que hacen uso de bucles while, do-while, for, etc.
Algo es recursivo si se define en términos de sí mismo (cuando para definirse hace mención a sí mismo). Para que una definición recursiva sea válida, la referencia a sí misma debe ser relativamente más sencilla que el caso considerado.
Ejemplo: definición de nº natural:
En un algoritmo recursivo distinguimos como mínimo 2 partes:
a). Caso trivial, base o de fin de recursión:
Es un caso donde el problema puede resolverse sin tener que hacer uso de una nueva llamada a sí mismo. Evita la continuación indefinida de las partes recursivas.
b). Parte puramente recursiva:
Relaciona el resultado del algoritmo con resultados de casos más simples. Se hacen nuevas llamadas a la función, pero están más próximas al caso base.
EJEMPLO ITERATIVO: int Factorial( int n ) { int i, res=1; for(i=1; i<=n; i++ ) res = res*i; return(res); } RECURSIVO: int Factorial( int n ) { if(n==0) return(1); return(n*Factorial(n-1)); }
int Fib( int n ) /* ej: Fibonacci */ { if(n<=1) return(1); return(Fib(n-1) + Fib(n-2)); }
int Ack( int n, int m ) /* ej: Ackerman */ { if(n==0 ) return(m+1); else if(m==0) return(Ack(n-1,1)); return(Ack(n-1, Ack(n,m-1))); }
Ej: Par o Impar: int par( int nump ) { if(nump==0) return(1); return( impar(nump-1)); } int impar( int numi ) { if(numi==0) return(0); return( par(numi-1)); }
La memoria del ordenador se divide (de manera lógica, no física) en varios segmentos (4):
Llamada a una función:
Llamada a una función recursiva:
En el caso recursivo, cada llamada genera un nuevo ejemplar de la función con sus correspondientes objetos locales:
a). Torres de Hanoi: Problema de solución recursiva, consiste en mover todos los discos (de diferentes tamaños) de una aguja a otra, usando una aguja auxiliar, y sabiendo que un disco no puede estar sobre otro menor que éste.
_|_ | | [___] | | [_____] | | [ ] | | ------------------------------------- A B C
/* Solucion: 1- Mover n-1 discos de A a B 2- Mover 1 disco de A a C 3- Mover n-1 discos de B a C */ void Hanoi( n, inicial, aux, final ) { if( n>0 ) { Hanoi(n-1, inicial, final, aux ); printf("Mover %d de %c a %c", n, inicial, final ); Hanoi(n-1, aux, inicial, final ); } }
b). Calcular x elevado a n de forma recursiva:
Solución: float xelevn( float base, int exp ) { if(exp == 0 ) return(1); return( base*xelevn(base,exp-1)); }
c). Multiplicar 2 nºs con sumas sucesivas recursivamente:
Solución: int multi( int a, int b ) { if(b == 0 ) return(0); return( a + multi(a, b-1)); }
d). ¿Qué hace este programa?:
void cosa( char *cad, int i) { if( cad[i] != '\0' ) { cosa(cad,i+1); printf("%c", cad[i] ); } } Solución: Imprime la cadena invertida.