En programación, se conoce como recursividad a la capacidad que tiene una función para llamarse a sí misma, con el propósito de resolver un problema dividiéndolo en subproblemas más pequeños, obteniendo así una solución al alcanzar el caso base. A diferencia de un bucle, una función recursiva no está basada en una declaración condicional iterativa sino en la llamada repetitiva de sí misma.

Las funciones recursivas suelen utilizarse para resolver problemas de naturaleza recursiva, que serían más difíciles o menos adecuados de abordar que con enfoques iterativos, como por ejemplo, los algoritmos de búsqueda y ordenación de datos. La elección entre usar una solución recursiva o iterativa depende en gran medida de la preferencia y experiencia del programador, la eficiencia y el tiempo de ejecución buscado, y sobre todo del tipo de problema que se va resolver.

DESVENTAJAS

Las funciones recursivas presentan algunas desventajas importantes frente a las técnicas iterativas, por lo que muchos programadores prefieren evitarlas, sin embargo, como se mencionó anteriormente, su uso depende del problema que se va a resolver. Entre sus desventajas comunes se encuentran:

- Mayor uso de pila de memoria: Cuando una función se llama a sí misma en repetidas ocasiones, se produce un mayor uso de memoria. Cada llamada crea una nueva instancia de la función y de sus variables locales en la pila de memoria, lo que puede significar un problema si se manejan grandes cantidades de datos.

- Dificultad de comprensión y de lectura: Las funciones recursivas requieren a menudo una comprensión profunda del problema y la lógica detrás del algoritmo, lo que puede dificultar su lectura y comprensión (especialmente para personas con pocos conocimientos en programación). 

- Riesgo de caer en bucles infinitos:  Si no se define correctamente el caso base se puede caer en bucles infinitos, lo que provocaría la saturación de la pila de memoria y consecuentemente el cuello de botella del programa.

- Rendimiento:  En algunos casos, las funciones recursivas pueden ser menos eficientes que otras técnicas de programación, ya que pueden requerir más tiempo de ejecución y recursos de memoria.

DISEÑO DE UNA FUNCIÓN RECURSIVA

No todas las funciones se pueden llamar a sí mismas, para lograrlo, se tienen que diseñar específicamente para ello, cumpliendo las siguientes 3 condiciones:

1.- Caso base de parada: el caso base es cualquier expresión en la que se le dice a la función cuándo dejar de llamarse a sí misma. Si no se define un caso base, la recursión producirá un bucle infinito.

2.- Inducción: Paso recursivo que provoca una llamada recursiva, debe ser correcto para distintos parámetros de entrada.

3.- Convergencia: Cada paso recursivo debe acercar a un caso base. Se describe el problema en términos de problemas más sencillos.T

Todas las funciones recursivas pueden convertir con enfoques iterativos y viceversa.

FUNCIONAMIENTO

Cada vez que se llama a una función recursiva desde la función principal, se crea un juego de variables locales, de este modo, si la función hace una llamada a sí misma, se guardan sus variables y parámetros, usando la pila, y la nueva instancia de la función trabajará con su propia copia de las variables locales. Cuando esta segunda instancia de la función retorna, recupera las variables y los parámetros de la pila, y continua la ejecución en el punto en que había sido llamada. Cuando se alcanza el caso base, se comienza a desapilar la pila y se van retornando los valores que fueron guardados previamente en la pila para cada una de las llamadas recursivas, obteniendo así la solución.

A continuación, veremos un ejemplo de función recursiva, aplicada en un programa que calcula la suma de los elementos de un arreglo:

#include <iostream>

int sum_array(int arr[], int size) {
    if (size == 0) { // Caso base: si el tamaño del arreglo es cero, devuelve cero
        return 0;
    } else {
        return arr[size - 1] + sum_array(arr, size - 1); // Se llama a la función sum_array pasando el arreglo y su tamaño menos uno como argumentos, y se suma el último elemento del arreglo
    }
}

int main() {
    int size;
    std::cout << "Ingrese el tamaño del arreglo: ";
    std::cin >> size;
    int arr[size];
    for (int i = 0; i < size; i++) {
        std::cout << "Ingrese un elemento: ";
        std::cin >> arr[i];
    }
    int sum = sum_array(arr, size);
    std::cout << "La suma de los elementos del arreglo es: " << sum << std::endl;
    return 0;
}

El programa hace lo siguiente: Primero solicita al usuario que ingrese el tamaño del arreglo y lo guarda en la variable 'size'. Luego, mediante un bucle 'for' llena el arreglo con los valores ingresados por el usuario guardandolos en el arreglo arr[]. Luego, se llama a la función 'sum_array' pasando el arreglo y su tamaño como argumentos. La función recursiva 'sum_array' utiliza una técnica de descomposición del problema en subproblemas más pequeños para calcular la suma de los elementos del arreglo. En ella hay que destacar que el caso base sería la condición:  if (size == 0). Y que la función se llama así misma en la línea  return arr[size - 1] + sum_array(arr, size - 1), tomando en cuenta que arr[size-1] indicaría el valor del elemento en el índice indicado, comenzando con 0 ya que los índices de un arreglo comienzan en 0, sum_array se llamaría a sí misma con los parámetros especificados.

Por ejemplo, si el usuario ingresa un arreglo de 3 elementos: 1,2,5. 'Size' tomaría el valor de 3 y el areglo el valor de arr[1,2,5], considerando que los índices del arreglo son los siguientes [10,21,52]. La función recursiva haría esto:

Primera llamada: sum_array([1, 2, 5], 3) -> 5 + sum_array([1, 2], 2)
Segunda llamada: sum_array([1, 2], 2) -> 2 + sum_array([1], 1)
Tercera llamada: sum_array([1], 1) -> 1 + sum_array([], 0)
Cuarta llamada: sum_array([], 0) -> 0

Al haber llegado al caso base (tamaño del arreglo cero), se comienza a desapilar las llamadas recursivas anteriores, sumando los valores retornados con el último elemento del arreglo:

sum_array([], 0) devuelve 0
sum_array([1], 1) devuelve 1 + 0 = 1
sum_array([1, 2], 2) devuelve 2 + 1 = 3
sum_array([1, 2, 5], 3) devuelve 5 + 3 = 8

En conclusión, se recomienda utilizar soluciones iterativas en lugar de funciones recursivas cuando la eficiencia es importante, cuando el problema no requiera este tipo de funciones, cuando se requiere una ejecución del algoritmo de manera frecuente o si no se poseen los conocimientos necesarios para manejar adecuadamente una función recursiva.

El código ha sido probado en Code::Blocks en Windows, por lo que es completamente funcional.

Puedes descargar el código .CPP aquí.

NOTA: Si al correr el programa los acentos o caracteres especiales no se muestran correctamente, puedes usar esta solución: ¿Cómo mostrar acentos y caracteres especiales en programas escritos en C++?