cplusplus.com: Sitio oficial de C++: Informacion, Referencias, Tutorial, Foro. (En inglés)
Minidosis.org: Curso de C++ con videos y lecturas.
conclase.net: Curso de C++
programar ya: Curso de C++ desde cero
cprogramming.com: C++ Tutorial (inglés).
Entorno de desarrollo integrado: fergarciac.wordpress.com
Compiladores, intérpretes y Máquinas virtuales.: latecladeescape.com
el hacker.net: Programación
Desarrollo web: Manual de iniciación a la programación.

En los distintos manuales incluimosm más webgrafía especifica de cada sección.

Donativos

Si este sitio te parece interesante puedes contribuir con una pequeña aportación.

Aprende Web por Anyelguti is licensed under a Creative Commons Reconocimiento-NoComercial-SinObraDerivada 3.0 Unported License.

5. Funciones

5.6. Recursividad

Definición

Se dice que una función es recursiva cuando dentro de su bloque de sentencias hay una llamada a la propia función.

En principio cualquer función puede hacerse una llamada a sí misma, sin embargo tiene que estar especialmente diseñada para que funcione correctamente, ya que al llamarse a sí misma provoca que ésta se vuelva a ejecutar, y dentro de sus instrucciones se vuelve a llamar, creando un bucle que si no está controlado se vuelve infinito.

Por lo tanto una función recursiva forma un bucle al ser llamada a si misma. Este bucle debe ser controlado de alguna manera para poder salir de él y no caer en estructuras indeseadas como bucles infinitos o estructuras que se autorreplican indefinidamente.

Recursividad condicionada: ejemplo 1

La forma más simple de hacer que una función recursiva no cree un bucle infinito es hacer que la llamada a sí misma esté dentro de una estructura condicional. De esta forma sólo si se cumplen ciertas condiciones la ejecución de la función se repite.

El siguiente ejemplo pide al usuario que pulse una tecla numérica. Mediante una función comprobamos la tecla pulsada. Si esta es un numero se sale de la función, pero si no lo es vuelve a pedir que se pulse una tecla, se llama a sí misma para volver a comprobarlo.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

#include<iostream>
using namespace std;

void comprobar(char r);

int main(){
    char c;
    cout << "Pulsa un numero : ";
    cin >> c;
    comprobar(c);
    cout << "Programa terminado." << endl;
}

void comprobar(char r){
     int n=int(r);
     if (n>=48 and n<=57) {
        cout << "Correcto, la tecla pulsada es un numero." << endl;
     }
     else {
        cout << "Incorrecto, la tecla pulsada NO es un numero." << endl;
        cout << "Vuelve a pulsar un numero : ";
        cin >>r;
        comprobar(r);
     }
}

El programa tiene una función recursiva, la cual crea un bucle del que no se sale hasta que el usuario pulsa una tecla numérica.

Observa cómo la llamada a la función dentro de la misma está dentro de una estructura condicional. Cuando se cumplen las condiciones marcadas por la condicional se sale del bucle, si no se cumplen, la función vuelve a repetirse.

Recursividad: ejemplo 2

En este ejemplo vamos a hacer que el usuario escriba una frase y nosotros la repetimos un determinado número de veces.

Evidentemente sería mucho más fácil resolver el problema utilizando un bucle, pero aquí se trata de ver cómo se puede resolver también mediante una función recursiva. Veamos el ejemplo :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

#include<iostream>
using namespace std;

void escribir(string frase, int n);

int main(){
    string f;
    int n=5;
    cout << "Escribe una frase. Yo la repetire 5 veces." << endl;
    getline(cin, f);
    cout << endl;
    escribir(f,n);
}

void escribir(string frase, int n){
    cout << n << " : " << frase << endl;
    n--;
    if (n>0) escribir(frase,n);
}

Observa como tenemos un número de control, n que en cada llamada va disminuyendo en una unidad.

A su vez el hecho de que se produzca o no la siguiente llamada a la función depende de que el número sea mayor que cero, por lo que cuando el número alcnce el cero, la función dejará de autorreplicarse.

Otro ejemplo: calcular factorial

El factorial de un número se define como la multiplicación de ese número por todos los que son menores que él. Sólo los números naturales (enteros positivos) pueden tener factorial. Por ejemplo, el factorial de 4 se define como 4*3*2*1. El factorial de 6 es 6*5*4*3*2*1.

Matemáticamente la operación factorial se define escribiendo un signo de admiración detrás del número: 4! = 4*3*2*1.

Por lo tanto los números negativos no tienen factorial, y además el factorial de cero es 1.

Con todo esto vamos a hacer una función recursiva que calcule el factorial de un número. El programa será el siguiente:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

#include<iostream>
using namespace std;

int factorial(int n);

int main(){
   int n, r;
   cout << "FACTORIAL : Escribe un numero : ";
   cin >> n;
   r=factorial(n);
   cout << n << "! = " << r << endl;
}

int factorial(int n) {
   if(n < 0) return 0;
   else if(n > 1) return n*factorial(n-1); // Recursividad: n>1
   return 1; // Condición para n == 1 y n == 0 
}

El programa calcula el factorial del número. Para números negativos devuelve el cero. Para el 0 y el 1 devuelve el 1, y para los demás números positivos, mediante la recursividad, vamos multiplicando cada número por el inmediatamente menor que si mismo hasta llegar a uno, para devolver el factorial.

En la siguiente página empezamos tema nuevo. En él veremos cómo organizar los datos para poder manejarlos mejor.

Estructuras de datos

Manual Básico de C++

Anterior siguiente ... Siguiente