Recursividad (Definición y conceptos).

   Existen al menos dos películas que, además de ser de mi agrado, ilustran excepcionalmente bien el concepto de recursividad:

1. Inception: aquí la recursividad se presenta debido a que dentro de un sueño, se puede estar soñando, incluso, quizá haya sabido de personas que sueñan que sueñan, eso es recursividad.
2. Being John Malcovich: uno de los personajes encuentra una especie de túnel que permite estar por unos minutos dentro de la mente de John Malcovich, y así poder ver lo que él ve, sentir lo que él siente, etc. John Malcovich se da cuenta de ello, y se introduce en el túnel que lleva a su propia mente. La recursividad radica en que la mente de John Malcovich es invadida por él mismo.

   Recursividad es la forma de especificar un proceso en función de su propia definición, y dicho proceso puede ser finito o infinito.

   Note que la definición de recursividad es recursiva.

   Para tener la especificación de un proceso finito, la especificación debe hacerse en términos de una simplificación del problema original, de tal forma que eventualmente se alcance un caso base o criterio de paro.

   Un proceso recursivo infinito se ilustra en la siguiente figura:

Recursividad infinita (aquí sólo hasta el nivel 3).

 

    Observe que del trazo inicial (Nivel 1) se puede generar el Nivel 2, repitiendo la misma figura del Nivel 1 en cada uno de los segmentos de recta o aristas del Nivel 1. Si este proceso se vuelve a aplicar (proceso recursivo) a las nuevas aristas generadas en el Nivel 2 se genera la figura del Nivel 3; y al menos en principio, potencialmente es posible repetir dicho proceso de manera infinita.

   Para el caso del ejemplo mostrado en la figura anterior sólo se ha llegado hasta el Nivel 3, generando de manera recursiva, una figura geométrica bastante interesante. Se deja como ejercicio al lector generar la figura geométrica correspondiente de Nivel 5.

Aspectos inherentes: overhead.

   Muchas funciones matemáticas como el factorial y la serie de Fibonacci por ejemplo, resultan útiles para ilustrar el concepto de recursividad, pero esto no quiere decir que la solución recursiva sea la más apropiada, de hecho es en general más ineficiente debido a que cada llamado de función lleva implícito un costo de gestión (overhead).

   ¿Se ha puesto a reflexionar lo que implica por ejemplo, cambiar el flujo de ejecución de un programa para procesar el código de una función?, ¿qué pasa cuando se llama a una función?, ¿cómo sabe la computadora a dónde tiene que regresar después de procesar el código de una función?, ¿cómo es que no se revuelven los datos de la función que llama con la función llamada si todos los datos se procesan en el mismo microprocesador? En este sentido, considere la siguiente figura:

Mecanismo de funcionamiento del llamado y retorno de una función.

 

    Cuando ocurre el llamado de una función, la secuencia de ejecución (flujo de control) cambia, y se da un salto hacia el código que define a dicha función (lo cual se ilustra con las flechas que van de izquierda a derecha en la figura anterior); sin embargo, dicho cambio no es tan simple como parece:

• El ámbito de una función es un nuevo contexto en todos los sentidos:
• Hay nuevas variables.
• Hay nuevas instrucciones y sentencias a procesar y todas ellas se ejecutan en el mismo microprocesador y utilizan el mismo conjunto de registros, por lo que antes de ejecutar la primera línea de código de una función, se debe respaldar el estado de todos los registros y la dirección de retorno (la dirección de la siguiente instrucción en la secuencia de ejecución que se estaba procesando antes del llamado a la función), y otros elementos que se utilizarán para procesar el nuevo contexto de ejecución (la función).
• Cuando la función termina, antes de regresar el control a donde estaba antes del llamado (ámbito del invocador), se deben restaurar en los registros todos los datos respaldados para que no exista ninguna afectación en la lógica de ejecución y de procesamiento de datos del ámbito del invocador. La ejecución debe de continuar como si nunca se hubiera cambiado de flujo de ejecución (lo cual se ilustra con las flechas que van de derecha a izquierda en la figura anterior).

   Aunque la descripción anterior es una versión sumamente reducida y resumida de lo que pasa con cada llamado de función, lo importante es tener en mente que atrás del llamado de una función suceden muchas muchas cosas, y a eso es a lo que se le llama, desde el punto de vista computacional costo de gestión de funciones (overhead).