49 - Recursividad: donde aplicar la recursividad

Problema donde conviene aplicar la recursividad

 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: programa179.c

Ver video

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

struct nodo {
    int info;
    struct nodo *sig;
};

struct nodo *raiz=NULL;


void insertarPrimero(int x)
{
    struct nodo *nuevo;
    nuevo=malloc(sizeof(struct nodo));
    nuevo->info = x;
    nuevo->sig = raiz;
    raiz = nuevo;
}

void imprimir(struct nodo *reco)
{
    if (reco != NULL)
    {
        imprimir(reco->sig);
        printf("%i ",reco->info);
    }
}

void liberar()
{
    struct nodo *reco = raiz;
    struct nodo *bor;
    while (reco != NULL)
    {
        bor = reco;
        reco = reco->sig;
        free(bor);
    }
}


int main()
{
    insertarPrimero(10);
    insertarPrimero(4);
    insertarPrimero(5);
    printf("Impresion de la lista del final al principio.\n");
    imprimir(raiz);
    liberar();
    getch();
    return 0;
}

Desde la main llamamos a la función imprimir y le pasamos la dirección del primer nodo de la lista.

El parámetro reco recibe en la primera llamada la dirección de raiz. Si reco es distinto a NULL llamamos recursivamente a la función 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.