Estructura de datos y Programación Año 2012.

RECURSIVIDAD

 Se

dice que un proceso es recursivo si se resuelve llamándose a si mismo.  La función no es recursiva para algunos valores del parámetro que se denominan casos base.  Toda función recursiva, debe tener algún caso base y toda llamada recursiva dentro de ella debe tender hacia el caso base.

En muchas ocasiones se puede ver que la recursión no es más que la repetición (iteración) de una serie de acciones. Esta iteración se da hasta llegar a un valor de una variable.  En la recursión esta iteración se esta desarrollando mediante la llamada de la función a sí misma con un parámetro que es la variable que determina el final de la recursión, en vez de ser un bucle dentro de una función normal. Así , en la iteración, el valor de una variable del bucle es la que determina cuando acabará la repetición; en la recursión es el parámetro. Por ejemplo: f(x) =( 1 x = 0 caso base. x · f(x − 1) x > 0 es una definición formal de la función factorial en forma recursiva que podría corresponder al algoritmo recursivo 1 int factorial(int n) { 2 if (0==n) 3 return 1; 4 else 5 return n * f(n-1); 6 } 

La pila (stack) y los registros de activación. El registro de activación de un procedimiento: es un bloque de memoria que contiene información sobre las constantes, variables locales declaradas en el procedimiento y los parámetros que se le pasen en esa llamada al procedimiento, junto con la dirección de retorno que corresponde a esa llamada. Los lenguajes de programación actuales utilizan una pila especial que el sistema tiene para las llamadas a subrutinas. En esta pila el código maquina del programa cada vez que tiene que llamar a un procedimiento guarda su registro de activación. Si dentro de esta subrutina se llama de nuevo a sí misma en forma recurrente, dado que la creación del registro de activación del propio procedimiento se hace sobre una pila sin borrar los registros de activación anteriores, se puede generar uno nuevo para cada llamada recursiva. Cuando una de las llamadas recursivas se resuelve por fin sin recursión, su registro de activación se ‘quita’ de la pila (se desapila), siguiendo la ejecución del programa por donde iba cuando se llamo esta última vez.





Debido a la sobrecarga (overhead) que producen las operaciones sobre la pila, la creación y borrado de los registros de activación, los procedimientos recursivos consumen más tiempo y memoria que los programas no recursivos. Solo en determinadas ocasiones, debido a la estructura de datos usada en el problema o al planteamiento del mismo la recursión es preferible, y evitar la recursión es bastante más difícil que dar una solución recursiva al problema.