Recursividad
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:
- El N º 0 es natural
- El Nº n es natural si n-1 lo es.
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)); }
Tipos de recursión
- Recursividad simple: Aquella en cuya definición sólo aparece una llamada recursiva. Se puede transformar con facilidad en algoritmos iterativos.
- Recursividad múltiple: Se da cuando hay más de una llamada a sí misma dentro del cuerpo de la función, resultando más dificil de hacer de forma iterativa.
int Fib( int n ) /* ej: Fibonacci */ { if(n<=1) return(1); return(Fib(n-1) + Fib(n-2)); }
- Recursividad anidada: En algunos de los argumentos de la llamada recursiva hay una nueva llamada a sí misma.
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))); }
- Recursividad cruzada o indirecta: Son algoritmos donde una función provoca una llamada a sí misma de forma indirecta, a través de otras funciones.
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 pila de recursión
La memoria del ordenador se divide (de manera lógica, no física) en varios segmentos (4):
- Segmento de código: Parte de la memoria donde se guardan las instrucciones del programa en cod. Máquina.
- Segmento de datos: Parte de la memoria destinada a almacenar las variables estáticas.
- Montículo: Parte de la memoria destinada a las variables dinámicas.
- Pila del programa: Parte destinada a las variables locales y parámetros de la función que está siendo ejecutada.
Llamada a una función:
- Se reserva espacio en la pila para los parámetros de la función y sus variables locales.
- Se guarda en la pila la dirección de la línea de código desde donde se ha llamado a la función.
- Se almacenan los parámetros de la función y sus valores en la pila.
- Al terminar la función, se libera la memoria asignada en la pila y se vuelve a la instruc. Actual.
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:
- La función se ejecutará normalmente hasta la llamada a sí misma. En ese momento se crean en la pila nuevos parámetros y variables locales.
- El nuevo ejemplar de función comieza a ejecutarse.
- Se crean más copias hasta llegar a los casos bases, donde se resuelve directamente el valor, y se va saliendo liberando memoria hasta llegar a la primera llamada (última en cerrarse)
Ejercicios
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.