Prog. Ricorsivo

di il
7 risposte

Prog. Ricorsivo

Ho il seguente programma:
 
 #include <stdio.h>

int main() {
    int c;
    if((c == getchar()) !=EOF) {
        main();
        printf("%c", c);
    }
}
 


Il testo mi chiede cosa è che fa questo programma, cioè mi chiede:

Che cosa fa il seguente programma? Che cosa accade se scambiate le righe 8 e 9?

La risposta è:

Riceve in ingresso un carattere e chiama ricorsivamente main() finché non viene inserito il
carattere EOF . Ogni carattere inserito viene poi stampato in ordine inverso. Se scambiate le
righe 8 e 9, i caratteri vengono visualizzati nell’ordine di input.
a b c
c b a


Ma io non sto riuscendo a capire come fa ad agire ricorsivamente?


-Quello che risesco a dire io, leggendo rigo per rigo è che si ha ovviamente la dichiarazione del main al rigo 3.

-Si ha la dichiarazione della variabile int c e che nel caso è un carattere.

-Si ha una condizione if che all'interno del quale si dichiara che se c viene letto come singolo carattere, (grazie alla funzione getchar()), e non si ha la fine del file (End Of File), allora si richiama il main.

-alla fine si stampa il carattere c.

Spero di aver decifrato bene gli step esecutivi!?!?

7 Risposte

  • Re: Prog. Ricorsivo

    Ma quando richiami il main cosa succede? Devi capire questo.

    La ricorsione è un concetto abbastanza complesso per chi inizia e non ha precise cognizioni di come lavori una chiamata di funzione. Per capirlo devi avere studiato il concetto di stack e di come funzioni lo stack durante l'esecuzione di un programma. Lo hai fatto?

    Supponi di seguire l'esecuzione del programma nel caso in cui inserisci il carattere a, poi il carattere b, poi EOF
  • Re: Prog. Ricorsivo

    oregon ha scritto:


    Ma quando richiami il main cosa succede? Devi capire questo.

    Mi viene di dire che se il main chiama il main è intesa come una ricorsione, e per fermare questo ciclico modo di chiamare e richiamare, ci vorranno delle condizioni, ma questa è una risposta che mi vien fuori intuitivamente!

    Per quanto riguarda lo stack, so che si riferisce alla pila di dati, (pila o stack)....., ma non trovo il nesso con il mio dubbio.....
  • Re: Prog. Ricorsivo

    Certo, la condizione sta nella if. In un caso la main non viene chiamata e la main termina.

    La CPU nell'eseguire il codice utilizza un'area di memoria detta stack in cui conserva dei dati e degli indirizzi di rientro per ogni chiamata.

    Per capire scrivi la sequenza delle linee eseguite nel caso che ti avevo suggerito.
  • Re: Prog. Ricorsivo

    oregon ha scritto:




    Per capire scrivi la sequenza delle linee eseguite nel caso che ti avevo suggerito.
    Perdonami, ma non sto capendo cosa dovrei fare!
  • Re: Prog. Ricorsivo

    Intanto mi sa che hai copiato male la linea della if che dovrebbe essere

    if((c = getchar()) !=EOF) {

    ma quello che ti chiedevo di fare è elencare le righe eseguite nel caso di esempio in cui facevi un input di 2 caratteri e dell'EOF. Inizio io e finisci tu

    1- inizia ad eseguire una prima volta la main
    2- prepara lo spazio per una variabile c
    3- esegue la getchar (accetta il carattere 'a' e lo memorizza nella variabile c)
    4- esegue la if e controlla che la variabile c sia diversa da EOF (è questo il caso)
    .......
  • Re: Prog. Ricorsivo

    Ciao,

    MT09_full ha scritto:


    Mi viene di dire che se il main chiama il main è intesa come una ricorsione, e per fermare questo ciclico modo di chiamare e richiamare, ci vorranno delle condizioni, ma questa è una risposta che mi vien fuori intuitivamente!
    ti consiglio di studiare la teoria delle funzioni ricorsive siccome da quel che scrivi sembra ti sfuggano alcune nozioni base delle stesse. Tieni inoltre presente che le funzioni ricorsive, come ti è stato detto, sono abbastanza complicate e se mancano alcuni concetti risultano estremamente ostiche. Prima di fare esercizi ti consiglio dunque di studiare un pò di teoria.

    Le funzioni ricorsive sono funzioni (lo saprai) che richiamano se stesse e nella loro costruzione c'è un caso di terminazione altrimenti la ricorsione continuerebbe all'infinito. Quindi non è che la risposta deve venirti intuitivamente ma dallo studio della teoria.

    MT09_full ha scritto:


    Per quanto riguarda lo stack, so che si riferisce alla pila di dati, (pila o stack)....., ma non trovo il nesso con il mio dubbio.....
    Non trovi il nesso siccome devi studiare attentamente la struttura dati Stack (o Pila in italiano) questo perchè le istanze di una funzione trovano spazio in un Pila seguendo la politica LIFO (Last In First Out).

    Ti consiglio di studiarti tale struttura e di come i dati (e le istanze delle funzioni) trovano spazio in essa e da essa vengono eliminate. Nella fattispecie una funzione rimane nella Pila finchè non è terminata (stato di esecuzione) e viene eliminata quando termina la sue esecuzione. Molto utile è le prime volte disegnarti la struttura nei vari passaggi guardando il codice.

    Questi sono spunti di studio che puoi approfondire.

    Dopo aver studiato questi concetti puoi guardare qualche esempio disegnando la struttura e vedendo cosa succede nella Pila. Poi pian piano gli esercizi si capiscono e sarai in grado di farli da solo (o con qualche dubbio legittimo). Molto utili sono stati per me quando studiavo la creazione di una funzione ricorsiva per il calcolo di una potenza di un numero e del fattoriale, ripeto, disegnando la struttura in ogni passo per capire come la Pila cambia quando si aggiunge una funzione e quando questa termina.

    Spero di averti aiutato

  • Re: Prog. Ricorsivo

    La definizione di funzione ricorsiva e' strettamente imparentata con il ""principio di induzione""


    https://it.wikipedia.org/wiki/Funzione_ricorsiv
Devi accedere o registrarti per scrivere nel forum
7 risposte