La recursividad sucede cuando un procedimiento o función se ejecuta a sí mismo. Cada vez que el procedimiento o función se ejecuta a sí mismo, se crean sus parámetros y variables locales en la Pila, por cada ejecución que se realice. Cuando se hace un procedimiento o función con recursividad, se debe usar una condición para detener las ejecuciones sucesivas del procedimiento ó función. Por ejemplo el siguiente programa:

Realiza una recursividad del procedimiento Infinito, pero el programa se ejecutará hasta que este deje de funcionar por falta de memoria en la Pila. El programa deja de funcionar cuando la Pila se llene, finalizando el programa bruscamente con un mensaje de error, impidiendo que se muestre el mensaje : FIN del programa.

Debido a que el procedimiento se ejecuta sucesivamente a sí mismo, sin ninguna condición entonces no existe la posibilidad de terminar con el procedimiento infinito que ejecuto al anterior, y eso hace que no se pueda destruir o liberar espacio en la Pila.

El siguiente programa es parecido al anterior, pero usa una condición para controlar la recursividad. A continuación el ejemplo:

En este caso el procedimiento Finito, usa una condición y se ejecuta asimismo sólo 9 veces, evitando que la pila se llene y el programa pueda continuar con su funcionamiento, mostrando el mensaje: FIN del programa.

La recursividad que hemos visto se conoce como recursividad simple o directa, existe otra caso de recursividad, que se conoce como recursividad indirecta o circular, esta se produce cuando un procedimiento o función ejecuta a otra, que a su vez terminará ejecutando de nuevo a la primera función o procedimiento. El siguiente programa muestra un ejemplo de recursión circular o indirecta:

Se puede observar que he declarado con anterioridad la cabecera del procedimientoB, con una palabra reservada forward, que le indica al compilador que este procedimiento se definirá más adelante en el programa.

Debido a que el procedimientoB se ejecuta dentro del ProcedimientoA, es necesario declararlo antes que B, pero no podríamos hacerlo porque el procedimientoB, necesita ejecutar al procedimientoA. Es por eso que se escribe sólo el encabezado del ProcedimientoB con la palabra reservada forward, para de esta manera poder usarlo en el ProcedimientoA. Obviamente se debe de escribir después el ProcedimientoB completo, ya que el uso de la palabra reservada forward, le indica al compilador que ese procedimiento se escribirá más adelante en el código fuente.

Algunos problemas matemáticos se pueden implementar con el uso de la recursividad simple o directa, como ejemplo tenemos el cálculo de factoriales, obtener el término n de la serie de Fibonacci, y el algoritmo recursivo de Ackermann. A continuación la implementación de los problemas matemáticos mencionados:

Las descripciones recursivas en las matemáticas se usan para describir algo, de tal manera que un ser humano sea capaz de entenderlo. Es por eso que son descripciones breves y concisas, para que se comprendan con relativa facilidad. Pero, cuando usamos la recursividad en la programación, nos encontramos con una serie de factores como la falta de memoria en la Pila, que impiden poner en práctica las descripciones recursivas. En esos casos es recomendable convertir una función o procedimiento recursivo en una función o procedimiento iterativo, siempre y cuando sea posible. A modo de ejemplo el cálculo del término n de la serie fibonacci en una función iterativa:

Otros ejemplos de recursividad directa o simple para mencionar serían: calcular el Máximo Común Divisor, las Torres de Hanoi, la suma de los elementos de un arreglo, Quick Sort, etc.