Recursividad: Problema donde conviene aplicar la recursividad

Tweet

En el concepto anterior se vieron pequeños problemas para entender como funciona la recursividad, pero no se desarrollaron problemas donde conviene utilizar la recursividad.

Problema 1:

Imprimir la información de una lista simplemente encadenada de atrás para adelante. El empleo de estructuras repetitivas para resolver este problema es bastante engorroso y lento (debemos avanzar hasta el último nodo e imprimir, luego avanzar desde el principio hasta el anteúltimo nodo y así sucesivamente) El empleo de la recursividad para este problema hace más sencillo su solución.

Programa:

#include <iostream>

using namespace std;

class ListaGenerica {
    class Nodo {
    public:
        int info;
        Nodo *sig;
    };
    Nodo *raiz;
    void imprimir(Nodo *reco);
public:
    ListaGenerica();
    ~ListaGenerica();
    void insertarPrimero(int x);
    void imprimir();
};

ListaGenerica::ListaGenerica()
{
    raiz = NULL;
}

ListaGenerica::~ListaGenerica()
{
    Nodo *reco = raiz;
    Nodo *bor;
    while (reco != NULL)
    {
        bor = reco;
        reco = reco->sig;
        delete bor;
    }
}


void ListaGenerica::insertarPrimero(int x)
{
    Nodo *nuevo = new Nodo();
    nuevo->info = x;
    nuevo->sig = raiz;
    raiz = nuevo;
}

void ListaGenerica::imprimir()
{
    imprimir(raiz);
}

void ListaGenerica::imprimir(Nodo *reco)
{
    if (reco != NULL) 
    {
        imprimir(reco->sig);
        cout<<reco->info << "-";
    }
}

void main()
{
    ListaGenerica *lg = new ListaGenerica();
    lg->insertarPrimero(10);
    lg->insertarPrimero(4);
    lg->insertarPrimero(5);
    lg->imprimir();
    delete lg;
    cin.get();
}

Este proyecto lo puede descargar en un zip desde este enlace :

RecursividadLista.zip

Desde la main llamamos al método imprimir sin parámetros que es el público.

Cuando llamamos al método recursivo le enviamos raiz y el parámetro reco recibe esta dirección.

Si reco es distinto a NULL llamamos recursivamente al método enviándole la dirección del puntero sig del nodo. Por lo que el parámetro reco recibe la dirección del segundo nodo.

Podemos observar como en las distintas llamadas recursivas el parámetro reco apunta a un nodo. Cuando se van desapilando las llamadas recursivas se imprime primeramente el 10 luego el 4 y por último el 5.

Síguenos por RSS

Puedes leerlos mediante el navegador Firefox, lectores de noticias en la computadora o el móvil o usando el servicio de Feedburner de Google para recibir las notificaciones por correo electrónico.
RSS - Suscribirse usando Feedburner de Google

Recibir las nuevas publicaciones de Boludo por email

Atom

.....

Protocolo  |  Mapa del Sitio  |  Report Abuse - DMCA  |  Términos y Condiciones  |  Ayuda  |  Privacidad de Datos  |  Política de Cookies  |  Reportar un bug  |  Licencia: CC BY-NC-ND 3.0