Visualizzazione dei risultati da 1 a 9 su 9
  1. #1

    [C] Problema funzioni ricorsive

    Ciao ragazzi? potete gentilmente spiegare come funziona questo stralcio di codice per n =4?
    Non mi è ancora chiaro il funzionamento.
    Vi ringrazio a tutti in anticipo.

    int funct (int n)
    {
    int i, ris = 0;
    if (n == 0)
    return 1;

    for (i = 1; i <= n; i *= 2)
    ris += i;

    ris += funct(n-1);

    return ris;
    }

  2. #2
    Se chiamo funct(4) restituirà:
    1+2+4+(1+2+(1+2+(1+(1)))).

    La funzione chiamata su 4 aggiunge a ris, inizialmente 0, le potenze di 2 inferiori o uguali a 4, partendo da 2^0 (dato che nel for l'incremento avviene raddoppiando): aggiunge quindi 1,2 e 4.
    A quel punto incrementa ris del valore della funzione calcolata per n = 3, che deve essere quindi eseguita.
    La funzione viene così chiamata su 3 e farà la stessa cosa sulla SUA istanza di ris incrementandola di 1 e poi 2, quindi del valore della funzione per n=2. Stessa cosa finché non avviene la chiamata su n = 0; che termina immediatamente ritornando 1.
    Quindi può concludere la funzione per n = 1, che ritorna funct(1) = 1+funct(0) = 2,
    poi la funzione per n = 2, che ritorna funct(2) = 1+2+funct(1) = 1+2+2 = 5,
    poi la funzione per n = 3, che ritorna funct(3) = 1+2+funct(2) = 1+2+5 = 8,
    poi la funzione per n = 4, che ritorna funct(4) = 1+2+4+funct(3) = 1+2+4+8 = 15.

  3. #3
    Grazie, purtroppo non ho ancora capito l'esercizio. devo entrare nell'ottica delle funzioni ricorsive.
    Potresti spiegarmelo meglio perfavore?

  4. #4
    Allora, cerca di capire che avviene nella memoria:
    Quando tu chiami funct(4), viene allocato lo spazio necessario alla funzione. In questo spazio ci saranno memorizzati i, n e ris relativi alla chiamata appena fatta. La funzione viene eseguita normalmente fino al punto in cui abbiamo

    codice:
    ris += funct(n-1);
    In questo momento, riguardo alla chiamata di funct(4), in memoria avremo i valori i = 8, n = 4, ris = 7.
    A questo punto ris deve essere incrementato di funct(n-1).
    L'unico modo per sapere quanto vale funct(n-1) = funct(3) è eseguire la funzione: l'esecuzione di funct(4) potresti quindi in un certo senso vederla come "sospesa", in attesa di sapere il risultato.
    Dobbiamo quindi eseguire funct(3) dall'inizio e il tutto avviene come sopra: si alloca lo spazio per delle nuove istanze di i, n e ris che saranno totalmente indipendenti da quelle precedenti, che giacciono per ora dimenticate più in basso nello stack. L'esecuzione della funzione su 3 prosegue indipendentemente e si arriverà di nuovo al punto in cui si deve eseguire

    codice:
    ris += funct(n-1);
    A quel punto la situazione in memoria sar� del tipo

    ---------- -|
    - 3 - n |
    ---------- |
    - 4 - i | -> appartengono a funct(3)
    ---------- |
    - 3 - ris |
    ---------- -|

    (altre cose che omettiamo)

    ---------- -|
    - 4 - n |
    ---------- |
    - 8 - i | -> appartengono a funct(4)
    ---------- |
    - 7 - ris |
    ---------- -|

    A questo punto la cosa si ripete finchè non si avrà la chiamata a funct(0)
    Questa volta non si esegue tutto il codice, ma si ritorna subito perchè nell'if iniziale c'è la condizione di uscita

    codice:
        
    if (n == 0)
        return 1;


    Nota che tutte le funzioni ricorsive devono avere un caso base, altrimenti si continua a chiamare all'infinito, senza mai terminare.
    In questo momento la situazione sarà del tipo:

    ---------- -|
    - 1 - n |
    ---------- |
    - 2 - i | -> appartengono a funct(1)
    ---------- |
    - 2 - ris | -----------> Qui è già stato aggiunto funct(0) che vale 1
    ---------- -|

    (altre cose che omettiamo)

    ---------- -|
    - 2 - n |
    ---------- |
    - 4 - i | -> appartengono a funct(2)
    ---------- |
    - 3 - ris |
    ---------- -|

    (altre cose che omettiamo)

    ---------- -|
    - 3 - n |
    ---------- |
    - 4 - i | -> appartengono a funct(3)
    ---------- |
    - 3 - ris |
    ---------- -|

    (altre cose che omettiamo)

    ---------- -|
    - 4 - n |
    ---------- |
    - 8 - i | -> appartengono a funct(4)
    ---------- |
    - 7 - ris |
    ---------- -|

    Funct(1) giunge così al termine, essendo stata calcolata funct(0).
    Viene quindi deallocato il suo spazio e il suo valore di ritorno viene sommato al ris di funct(2)

    ---------- -|
    - 2 - n |
    ---------- |
    - 4 - i | -> appartengono a funct(2)
    ---------- |
    - 5 - ris |
    ---------- -|

    (altre cose che omettiamo)

    ---------- -|
    - 3 - n |
    ---------- |
    - 4 - i | -> appartengono a funct(3)
    ---------- |
    - 3 - ris |
    ---------- -|

    (altre cose che omettiamo)

    ---------- -|
    - 4 - n |
    ---------- |
    - 8 - i | -> appartengono a funct(4)
    ---------- |
    - 7 - ris |
    ---------- -|

    Può terminare quindi funct(2) e il valore che ritorna lo sommiamo al ris di funct(3)




    ---------- -|
    - 3 - n |
    ---------- |
    - 4 - i | -> appartengono a funct(3)
    ---------- |
    - 8 - ris |
    ---------- -|

    (altre cose che omettiamo)

    ---------- -|
    - 4 - n |
    ---------- |
    - 8 - i | -> appartengono a funct(4)
    ---------- |
    - 7 - ris |
    ---------- -|

    Infine termina funct(3) e il suo valore di ritorno è sommato al ris di funct(4)

    ---------- -|
    - 4 - n |
    ---------- |
    - 8 - i | -> appartengono a funct(4)
    ---------- |
    - 15 - ris |
    ---------- -|

    funct(4) ritorna il suo ris = 15.

    Spiegarlo scrivendo non è così facile. Ti consiglio di cercare in giro qualche animazione che lo faccia visualizzare bene e che utilizzi qualche funzione che abbia un senso pratico più evidente di questo, come la successione di Fibonacci (fib(n) = fib(n-1) + fib(n-2)) o il calcolo di un fattoriale (fatt(n) = n*fatt(n-1)).
    In alternativa puoi usare un debugger visuale e scorrere le istruzioni del programma vedendo in che ordine sono eseguite e come cambiano le variabili.



    NOTA: il forum ha collassato tutti gli spazi multipli nei "disegnini", comunque sia il senso è che ogni blocchetto appartiene ad un' istanza diversa della funzione

    Ultima modifica di scimmiaparlante; 08-05-2018 a 16:38

  5. #5
    Utente di HTML.it L'avatar di oregon
    Registrato dal
    Jul 2005
    residenza
    Roma
    Messaggi
    36,352
    Questi concetti possono non essere semplici da comprendere (almeno non immediati), se non hai CHIARISSIMO il funzionamento dello STACK e di come questo interviene tra le varie chiamate delle funzioni (ricorsive o non).

    Se pensi di non essere sicurissimo del suo funzionamento, fai un passo indietro e studia bene lo STACK e la sua importanza nella chiamata di funzioni.
    No MP tecnici (non rispondo nemmeno!), usa il forum.

  6. #6
    è meglio forse usare qualche programma che mi mostra le varie istruzioni. Sapresti consigliarmi qualcuno? Grazie di cuore

  7. #7
    ma bisogna partire da n=4, e poi scendere sino ad arrivare ad n=0 giusto??

  8. #8
    Utente di HTML.it L'avatar di oregon
    Registrato dal
    Jul 2005
    residenza
    Roma
    Messaggi
    36,352
    Non usi un ambiente di compilazione integrato con debugger?
    No MP tecnici (non rispondo nemmeno!), usa il forum.

  9. #9
    no per il momento. mi potresti consigliare qualcuno?

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2020 vBulletin Solutions, Inc. All rights reserved.