Estructura de datos: conceptos básicos de recursividad

Algunos lenguajes de programación de computadoras permiten que un módulo o función se llame a sí mismo. Esta técnica se conoce como recursividad. En recursividad, una funciónα o se llama a sí mismo directamente o llama a una función β que a su vez llama a la función original α. La funciónα se llama función recursiva.

Example - una función que se llama a sí misma.

int function(int value) {
   if(value < 1)
      return;
   function(value - 1);

   printf("%d ",value);   
}

Example - una función que llama a otra función que a su vez la vuelve a llamar.

int function1(int value1) {
   if(value1 < 1)
      return;
   function2(value1 - 1);
   printf("%d ",value1);   
}
int function2(int value2) {
   function1(value2);
}

Propiedades

Una función recursiva puede ser infinita como un bucle. Para evitar la ejecución infinita de una función recursiva, hay dos propiedades que debe tener una función recursiva:

• Base criteria - Debe existir al menos un criterio o condición base, de manera que, cuando se cumpla esta condición, la función deje de llamarse a sí misma de forma recursiva.

• Progressive approach - Las llamadas recursivas deben progresar de tal forma que cada vez que se haga una llamada recursiva se acerque más al criterio base.

Implementación

Muchos lenguajes de programación implementan la recursividad mediante stacks. Generalmente, siempre que una función (caller) llama a otra función (callee) o en sí misma como destinatario de la llamada, la función de llamada transfiere el control de ejecución al destinatario de la llamada. Este proceso de transferencia también puede implicar que algunos datos se pasen de la persona que llama a la persona que llama.

Esto implica que la función de llamada tiene que suspender su ejecución temporalmente y reanudarla más tarde cuando el control de ejecución regresa de la función de llamada. Aquí, la función de llamada debe comenzar exactamente desde el punto de ejecución en el que se pone en espera. También necesita exactamente los mismos valores de datos en los que estaba trabajando. Para ello, se crea un registro de activación (o marco de pila) para la función de llamada.

Este registro de activación mantiene la información sobre variables locales, parámetros formales, dirección de retorno y toda la información que se pasa a la función de llamada.

Análisis de recursividad

Se puede argumentar por qué utilizar la recursividad, ya que la misma tarea se puede realizar con la iteración. La primera razón es que la recursividad hace que un programa sea más legible y, debido a los últimos sistemas mejorados de CPU, la recursividad es más eficiente que las iteraciones.

Complejidad del tiempo

En caso de iteraciones, tomamos el número de iteraciones para contar la complejidad del tiempo. Del mismo modo, en caso de recursividad, asumiendo que todo es constante, intentamos averiguar la cantidad de veces que se realiza una llamada recursiva. Una llamada realizada a una función es Ο (1), por lo tanto, el número (n) de veces que se realiza una llamada recursiva hace que la función recursiva Ο (n).

Complejidad espacial

La complejidad del espacio se cuenta como la cantidad de espacio adicional que se requiere para que se ejecute un módulo. En caso de iteraciones, el compilador apenas requiere espacio adicional. El compilador sigue actualizando los valores de las variables utilizadas en las iteraciones. Pero en caso de recursividad, el sistema necesita almacenar el registro de activación cada vez que se realiza una llamada recursiva. Por tanto, se considera que la complejidad espacial de la función recursiva puede ser mayor que la de una función con iteración.