La recursividad es la técnica de programación en la que se implementa un algoritmo que se resuelve llamándose a sí mismo. El comportamiento de una función recursiva depende de sus parámetros y es como un resorte que se amplía, hasta una constante K que se llamará tope, y luego vuelve a su estado original, realizando un proceso en las dos acciones.

Entre los tipos de recursividad se destacan:

• Simple: donde solo aparece una llamada recursiva y se transforma en algoritmos interactivos.
• Múltiple: en la que se realiza más de una llamada a sí misma en la función y a otras funciones.

La programación clásica utiliza la programación To-Down y estructurada. Pero se utilizará la programación recursiva para un mejor el rendimiento de los procesos; ejemplo de ello es Prolog, un lenguaje que en un 90% utiliza la recursividad para aumentar el rendimiento, efectividad y confiabilidad de los procesos.

Por su parte, la técnica “divide y vencerás” es un método que fracciona el problema en dos o más subproblemas similares, hasta que se logre entender y resolver. Esta técnica también se conoce como recursión múltiple.

Al finalizar la unidad, el estudiante estará en condiciones de responder a las siguientes preguntas:

• ¿Qué es recursividad y como se aplica?
• ¿Cuál es técnica divide y vencerás?
• ¿Cuándo utilizar la recursividad?
• ¿Cuándo no usar la recursividad?
• ¿Cuáles son los problemas que se puede incurrir al utilizar algoritmos recursivos?

Objetivo general

Desarrollar algoritmos recursivos para la resolución de problemas.

Objetivos específicos

• Diseñar algoritmos mediante las técnicas de divides y vencerás para la resolución de problemas.
• Utilizar la recursividad en algoritmos para el mejoramiento de la eficiencia.

Se emplea en el diseño de algoritmos para la resolución de problemas a partir de la división de sub-problemas del mismo tipo, pero con menor tamaño. Si los sub-problemas se mantienen grandes, se aplicarán de nuevo para obtener sub-problemas pequeños para ser solucionados con la implementación de recursión.

Básicamente la técnica divide y vencerás (DV) consiste en:

• Descomponer el caso a resolver en un cierto número de sub-casos más pequeños del mismo problema.
• Resolver sucesiva e independientemente todos estos sub-casos.
• Combinar las soluciones obtenidas para obtener la solución del caso original.

Características

• Sub-problemas del mismo tipo que el original.
• Los sub-problemas se resuelven independientemente.
• No existe solapamiento entre sub-problemas.

Condiciones para que DV sea óptimo

• Selección de cuando utilizar el algoritmo ad hoc, calcular el umbral de recursividad.
• Poder descomponer problema en sub-problemas y recombinar de forma eficiente a partir de las soluciones parciales.
• Los sub-casos deben tener aproximadamente el mismo tamaño.

Se trata de la forma en que se especifica un proceso basado en su propia definición. Recursividad es la posibilidad de definir un tipo de datos en términos de sí mismo y esto permite establecer instancias complejas de un proceso en términos de instancias más simples y de una o más instancias finales definidas explícitamente.

Un algoritmo recursivo es aquel que expresa la solución de problemas en sí mismo y de una solución simple conocida; ésta, es una referencia que permite completar la solución en una cantidad finita de pasos. Los algoritmos recursivos pueden adoptar la forma de funciones que retornan un valor o que causan un efecto.

Las funciones son procesos que puede tener parámetros resolviendo por si mismas o llamando a otras funciones para resolver una problemática, pudiéndose llamar a si misma recursivamente. Los algoritmos recursivos que tienen las llamadas al final, se dice que tienen recursividad final.

Las funciones recursivas se clasifican en:

• Recursividad directa: se llama a sí mismo (método de recursividad simple) o en varias partes del programa (recursividad múltiple).
• Recursividad indirecta o mutua: dos métodos se llaman entre sí.

A manera de contextualización, se sugiere ver la siguiente galería con el paso a paso de la creación de un algoritmo de recursividad.

Material de apoyo

En la recursividad simple, dentro del módulo recursivo, existe una única invocación a sí mismo, como sucede en el caso de la función factorial. En general, los módulos recursivos simples son fácilmente transformados a su versión iterativa.

Llamada a una función recursiva

En cada llamada se genera un nuevo ejemplar de la función con sus objetos locales:

• La función se ejecuta normalmente hasta la llamada a sí misma. Se crean en la pila de recursión nuevos parámetros y variables locales con los mismos nombres.
• El nuevo proceso de función comienza a ejecutarse.
• Se crean varias 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).

En la recursividad múltiple, el módulo se invoca a sí mismo más de una vez dentro de una misma activación. Este tipo de módulos son más difíciles de llevar a su forma iterativa. Algunos ejemplos de funciones recursivas múltiples son la función que implementa la sucesión de Fibonacci y la de las Torres de Hanoi.

Como una variante de la recursión múltiple se puede tener recursión anidada, que ocurre cuando dentro de una invocación recursiva ocurre como parámetro otra invocación recursiva. Un ejemplo de esto puede verse en la de Ackerman.

Esta se da cuando alguna llamada recursiva recibe como parámetro a otra llamada recursiva:

Donde:

• R: Función recursividad
• m: Parámetro
• B: Condición booleana del parámetro
• H: Transformación del parámetro
• P: Transformación de la función recursiva
• K: Transformación del parámetro

Se puede decir que la recursividad es una técnica de programación bastante útil y muy interesante de estudiar. A través de los temas abordados y los ejemplos el futuro programador está en la capacidad de incluir esta técnica cuando se le presente un problema.

La asignación de memoria, sea estática o dinámica, en realidad se tendrá que aplicar en cualquier programa al momento de su codificación, teniendo en cuenta que cada programador tiene su estilo de programar.

Conocer qué es la recursividad y cómo utilizarla es bastante útil para el programador en su que hacer para solucionar problemas por medio de algoritmos, eficientes, eficaces, de fácil mantenimiento y entendimiento.

En la cotidianidad existe un caso que permite interpretar a la recursividad y hasta dónde se puede llegar con ella: es el de las muñecas Matrushka.