Recursividad C++

Recursividad en C++

Recursividad en C++:

La recursividad es una técnica de programación elemental que permite que una función pueda llamarse asimismo desde la misma función. Se puede utilizar la recursividad como una alternativa a la iteración. La recursividad es una herramienta poderosa e importante en la resolución de problemas en programación. Una solución recursiva es normalmente menos eficiente en términos de tiempo de computadora que una solución iterativa debido a las operaciones auxiliares que llevan consigo las llamadas suplementarias a las funciones: sin embargo, en muchas circunstancias el uso de la recursión permite a los programadores especificar las soluciones naturales, más lógicas, elegantes, sencillas, que serían, en caso contrario difícil de resolver.

No todas las funciones pueden llamarse a sí mismas, sino que deben estar diseñadas especialmente para que sean recursivas, de otro modo podrían conducir a bucles infinitos, o a que el programa termine inadecuadamente. Tampoco todos los lenguajes de programación permiten usar recursividad. C++ permite la recursividad.

Cada vez que se llama a una función, 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 continúa la ejecución en el punto en que había sido llamada.

Por ejemplo para calcular el factorial de cualquier número mayor que cero hay que calcular como mínimo el factorial de otro número. La función que se utiliza es la función en la que se encuentra en estos momentos, esta función debe llamarse a sí misma para el número menor inmediato, para poder ejecutarse en el número actual. Esto es un ejemplo de recursividad.

De esta forma podríamos crear una función recursiva para calcular el factorial de un número entero.

El factorial se simboliza como n!, se lee como "n factorial", y la definición es:

n! = n * (n-1) * (n-2) * ... * 1

Hay algunas limitaciones:

No es posible calcular el factorial de números negativos, no está definido.

El factorial de cero es 1.

De modo que una función bien hecha para cálculo de factoriales debería incluir un control para esos casos:

/* Función recursiva para cálculo de factoriales */

int factorial(int n) {

if(n < 0) return 0;

else

if(n > 1) return n*factorial(n-1); /* Recursividad */

return 1; /* Condición de terminación, n == 1 */

}

Veamos paso a paso, lo que pasa cuando se ejecuta esta función, por ejemplo: factorial (4):

1aInstancia

n=4

n>1

salida ← 4 * factorial (3) (Guarda el valor de n = 4)

2aInstancia

n>1

salida ← 3*factorial (2) (Guarda el valor de n = 3)

3aInstancia

n>1

salida ← 2*factorial (1) (Guarda el valor de n = 2)

4aInstancia

n == 1 → retorna 1

3aInstancia

(recupera n=2 de la pila) retorna 1*2=2

2aInstancia

(recupera n=3 de la pila) retorna 2*3=6

1aInstancia

(recuperan=4delapila)retorna6*4=24

Valor de retorno → 24

Aunque la función factorial es un buen ejemplo para demostrar cómo funciona una función recursiva, la recursividad no es un buen modo de resolver esta función, que sería más sencilla y rápida con un simple bucle for.

Una función recursiva tiene generalmente dos partes:

1) Una llamada recursiva con parámetros más sencillos.

2) Una parte de terminación que detiene la recursividad.

Principios de la recursividad:

La recursividad es una de las formas de control más importantes en la programación. Los procedimientos recursivos son la forma más natural de representación de muchos algoritmos.

El concepto de recursividad está ligado, en los lenguajes de programación, al concepto de procedimiento o función. Un procedimiento o función es recursivo cuando durante una invocación a él puede ser invocado a su vez él mismo.

El conocimiento de los principios fundamentales de la recursividad evita evadir su utilización cuando su aplicación sea conveniente para un determinado problema.

El uso de la recursividad es particularmente conveniente para aquellos problemas que pueden definirse de modo natural en términos de recursividad.

Ventajas y desventajas de la Recursividad:

Ventajas:

· No es necesario definir la secuencia de pasos exacta para resolver el problema.

· Soluciones simples, claras.

· Soluciones elegantes.

· Soluciones a problemas complejos.

Desventajas:

· Podría ser menos eficiente.

· Sobrecarga asociada con las llamadas a subalgoritmos

· Una simple llamada puede generar un gran número de llamadas Recursivas. (Fact(n) genera n llamadas recursivas)

· El valor de la recursividad reside en el hecho de que se puede usar para resolver problemas sin fácil solución iterativa.

· La ineficiencia inherente de algunos algoritmos recursivos.

Ejemplos de funciones recursivas en C++:

1. // Sumar los dígitos de un número

#include <iostream>

using namespace std;

int SumaDigitos(int);

int main() {

cout << 32890123 << ": " << SumaDigitos(32890123) << endl;

return 0;

}

int SumaDigitos(int n) {

if(n < 10) return n;

return n%10+SumaDigitos(n/10);

}

2. // El producto de forma recursiva

#include <iostream>

using namespace std;

int producto(int a, int b){

if (b==0)

return 0;

else

return a+producto(a,b-1);

}

3. // Suma recursiva de los elementos de un vector

#include <iostream>

using namespace std;

int SumaV (int *V, int n){

if (n==0)

return V[0];

else

return V[n]+sumaV(V,n-1);

}

4. // Buscar el máximo de un vector (I)

#include <iostream>

using namespace std;

int Mayor1 (int *V, int n){

int aux;

if (n==0)

return

...