Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Funzioni ricorsive, come funzionano?
Forum - C/C++ - Funzioni ricorsive, come funzionano?

Avatar
Soulcyber (Normal User)
Newbie


Messaggi: 1
Iscritto: 19/09/2011

Segnala al moderatore
Postato alle 11:52
Lunedì, 19/09/2011
Ciao ragazzi, sono qui per chiedere il vostro aiuto, volevo sapere se qualcuno era in grado di spiegarmi come funzionano le funzioni ricorsive, preavviso subito che ho letto tutto quello che ho trovato cercando normalmente su internet, tipo esempi sul fattoriale, fibonacci ecc ecc, ma non ho trovato nulla di complesso che mi aiutasse a capire come funziona quando il codice è più complicato..

Codice sorgente - presumibilmente C++

  1. truct Cella {
  2. int valore;
  3. struct Cella *next;
  4. }
  5.  
  6. typedef struct Cella *Lista;



Ho una lista L1->8-5-2-7-4->NULL e una lista L2->NULL (vuota)
ad un certo punto del main mi viene chiamata la funzione:

Codice sorgente - presumibilmente Plain Text

  1. L2 = elabora(L1,0,L1);


e la funzione elabora è la seguente:

Codice sorgente - presumibilmente C++

  1. Lista elabora (Lista LL, int f, Lista tt)
  2. {
  3.         Lista aux;
  4.         If (LL == NULL)
  5.               return NULL;
  6.  
  7.         If (f)
  8.         {
  9.               aux = elabora(LL->next,(f+1)%2,tt);
  10.               LL->next = aux;
  11.               return LL;
  12.         }
  13.         else
  14.         {
  15.               aux = elabora(LL->next,(f+1)%2,LL);
  16.               if (tt != LL)
  17.                        tt->next = LL;
  18.               return aux;
  19.         }
  20. }



ecco posso dirvi che la soluzione è questa
L1->8-2-3->NULL
L2->5-7->NULL

ma non riesco a capire i passaggi che fa, proprio il meccanismo con cui crea le istanze della funzione e come le risolve al contrario partendo dall'ultima

Se qualcuno ha un po' di tempo da perdere nello spiegarmelo ve ne sarei grato^^
Grazie comunque, ciao a tutti :)

PM
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 6380
Iscritto: 03/01/2010

Up
3
Down
V
Segnala al moderatore
Postato alle 14:01
Lunedì, 19/09/2011
Ti consiglio di studiare il concetto di

stack

(e non mi dire che lo conosci bene perché non avresti questi dubbi sulle funzioni ricorsive)

Perdonami...che c'entrano le pile con le funzioni ricorsive? - mattia1481 - 19/09/11 14:25
c'entrano perchè lo stack contiene i parametri delle chiamate ricorsive, esattamente nell'ordine di valutazione. Studiare lo stack automaticamente risolve il flowchart di esecuzione della ricorsione. - TheKaneB - 19/09/11 14:38
Sono stato anticipato ... mattia ... hai detto che il meccanismo non è tanto difficile da comprendere, ma senza il concetto di stack, tu come l'hai capito? - nessuno - 19/09/11 14:43
Quando a suo tempo studiai l'argomento sul manuale VISUAL BASIC 6 della Mc Graw Hill, nel capitolo della ricorsione non ricordo che si citassero gli Stack. - mattia1481 - 19/09/11 14:52
ci vuole un libro di algoritmi specifico, non va bene un manuale di un linguaggio, che sugli algoritmi potrà darti soltanto un'infarinatura superficiale. - TheKaneB - 19/09/11 14:56


Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
---
Il grande studioso italiano Bruno de Finetti (uno dei padri fondatori del moderno Calcolo delle probabilità) chiamava il gioco del Lotto Tassa sulla stupidità.
PM
Avatar
gigisoft (Member)
Guru


Messaggi: 696
Iscritto: 11/10/2008

Up
3
Down
V
Segnala al moderatore
Postato alle 14:24
Lunedì, 19/09/2011
A prescindere dall'esempio postato, una funzione ricorsiva serve per risolvere un problema di ordine n riducendolo a uno o piu' sottoproblemi di ordine m < n, finche' tutti i sottoproblemi non sono di ordine talmente basso che possono essere banalmente risolti;

per esempio consideriamo il fattoriale n! come problema di ordine n
chiamiamolo p(n)

siamo in grado di risolverlo se l'ordine n e' 0 o 1
P(1) = 1! = 1; e p(0) = 0! = 1;

dopodiche' consideriamo il problema p(n), di ordine n > 1; possiamo ridurlo a un problema p(n - 1) di ordine (n - 1), cosi':
p(n) = n * p(n - 1)

dopodiche' se (n - 1) e' abbastanza basso da risolvere il problema, ok, se no si continua a ridurre l'ordine del problema; in pratica:

Codice sorgente - presumibilmente C++

  1. int Factor(int N)
  2. {
  3.  // Controllo se l'ordine del problema e'
  4.  // sufficientemente basso per risolverlo
  5.  if ((N == 0) || (N == 1))
  6.     {
  7.       return 1;  // Se e' cosi' lo risolvo banalmente
  8.     }
  9.   else
  10.     {
  11.       return N * Factor(N - 1) // Altrimenti provo a ridurlo a un ordine piu' basso
  12.     }
  13. }



Ragiona in questo senso, dovrebbe riuscirti piu' facile capire.
Ciao. :k:

Luigi






Ultima modifica effettuata da gigisoft il 19/09/2011 alle 14:26
[Mi piace] - mattia1481 - 19/09/11 14:28
PM
Avatar
Ultimo (Member)
Guru


Messaggi: 877
Iscritto: 22/05/2010

Up
2
Down
V
Segnala al moderatore
Postato alle 15:42
Lunedì, 19/09/2011

Non vorrei dire una cazzata, ma in .NET se usi la ricorsione, cioè una funzione

che richiama se stessa, se non imposti correttamente un codice di controllo

ti verrà generata un eccezzione sullo Stack, è corretto ? :yup:

Non proprio... - mattia1481 - 19/09/11 15:45
Corretto. Avresti uno StackOverflow ... almeno tutti noi lo avremmo, tranne mattia ... - nessuno - 19/09/11 15:46
ahaha - Ultimo - 19/09/11 15:47
Mi spigo meglio, il .net solleverà un'eccezione nel momento in cui la funzione ricorsiva avrà riempito quello che è la "memoria gestita", se il codice ne esce prima non verrà sollevata alcuna eccezione. - mattia1481 - 19/09/11 15:48
azz...che pessimo Italiano! - mattia1481 - 19/09/11 15:49
Mattia ... ma ci prendi in giro? Gestitto o non gestito è uno stack ... e ti è stato detto "se non imposti correttamente un codice di controllo" proprio per evidenziare il problema sullo stack ... - nessuno - 19/09/11 15:50
Io non prendo in giro nessuno, la mia è stata solo una precisazione. - mattia1481 - 19/09/11 15:52
grazie mille, sono andato a rileggere lo stack di sistema e in effetti ho capito qualcosa in più :) - Soulcyber - 19/09/11 15:52
Quale precisazione? Ripeto, non fossi stato chiaro, gestita o non gestita si tratta di memoria dedicata ad uno stack. Pensa al C per non avere problemi di memoria gestita o no ... - nessuno - 19/09/11 15:53
Solo come battuta (senza offesa) ... se tu avessi iniziato un discorso simile ad un mio esame, non te lo avrei fatto neanche iniziare ... - nessuno - 19/09/11 15:54
@ Soulcyber ... non c'è di che ... - nessuno - 19/09/11 15:57


If ok Then GOTO Avanza else GOTO Inizia

PM
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 6380
Iscritto: 03/01/2010

Up
1
Down
V
Segnala al moderatore
Postato alle 15:04
Lunedì, 19/09/2011
Studiare la ricorsione su un libro di VB6 è piuttosto anomalo ... è come studiare i meccanismi di riproduzione del DNA su un'enciclopedia medica per ragazzi ...

Lo "stack di sistema" (che è quello di cui parlo, non in genere uno stack) è fondamentale per il funzionamento di "codice ricorsivo". Studialo su testi adeguati.

Ultima modifica effettuata da nessuno il 19/09/2011 alle 15:10
...mi fido di quello che dici, io comunque l'ho imparato lo stesso cos'è una funzione ricorsiva :-) - mattia1481 - 19/09/11 15:08
Beh ... sicuramente saprai cos'è, ma non conosci i meccanismi profondi ... - nessuno - 19/09/11 15:12
profondi? - mattia1481 - 19/09/11 15:14
Se profondi ti sembra strano, diciamo "dal punto di vista del sistema" ... - nessuno - 19/09/11 15:26


Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
---
Il grande studioso italiano Bruno de Finetti (uno dei padri fondatori del moderno Calcolo delle probabilità) chiamava il gioco del Lotto Tassa sulla stupidità.
PM
Avatar
mattia1481 (Member)
Pro


Messaggi: 84
Iscritto: 03/11/2008

Up
0
Down
V
Segnala al moderatore
Postato alle 13:16
Lunedì, 19/09/2011
A prescindere dall'esempio che hai postato, il meccanismo di una funzione ricorsiva non è poi così difficile da comprendere, non è altro che una funzione che nel suo corpo richiama se stessa fino a quando il valore restituito non soddisfa una determinata condizione.

Ciao.

PM
Avatar
mattia1481 (Member)
Pro


Messaggi: 84
Iscritto: 03/11/2008

Up
-1
Down
V
Segnala al moderatore
Postato alle 15:30
Lunedì, 19/09/2011
Guarda, questa è parte della definizione che Wikipedia da della ricorsione : "... L'algoritmo richiama se stesso generando una sequenza di chiamate che ha termine al verificarsi di una condizione particolare che viene chiamata condizione di terminazione..."

Credo proprio di non sbagliare se dico e ribadisco che la ricorsione prescinda dagli "stack" che hai citato poc'anzi.

Ciao.

E invece sbagli. Se non ti spieghi "in pratica" come faccia a "richiamare sè stesso" e dove risieda in pratica quella "sequenza di chiamate" , non capisci a fondo il meccanismo. - nessuno - 19/09/11 15:36
ops ... prescinde - mattia1481 - 19/09/11 15:37
In ogni caso ... libero di pensarla come vuoi ... ma cambierai idea quando avrai il tuo primo "out of memory" dalla tua funzione ricorsiva ... - nessuno - 19/09/11 15:38
PM
Avatar
mattia1481 (Member)
Pro


Messaggi: 84
Iscritto: 03/11/2008

Up
-2
Down
V
Segnala al moderatore
Postato alle 14:51
Lunedì, 19/09/2011
Quando a suo tempo studiai l'argomento sul manuale VISUAL BASIC 6 della Mc Graw Hill, nel capitolo della ricorsione non ricordo che si citassero gli Stack.

PM
Avatar
mattia1481 (Member)
Pro


Messaggi: 84
Iscritto: 03/11/2008

Up
-2
Down
V
Segnala al moderatore
Postato alle 16:34
Lunedì, 19/09/2011
Risposta per "nessuno"

1)
La mia precisazione è :
la funzione ricorsiva nel .net non solleva per forza un'eccezione del tipo StackOverflow se non viene gestita correttamente, ma solo nel momento in cui "sfora" la memoria che gli è stata assegnata dal gestore della memoria gestita (scusate la ripetizione), se il codice esce dalla funzione prima che questo avvenga, non verrà sollevata l'eccezione di tipo StackOverflow.
Ora è chiara la mia precisazione?

2)
Il post sull' "Esame" te lo potevi risparmiare, a giudicare da come scrivi, sei un ragazzino che nella vita ne deve superare ancora tanti di esami, e non mi riferisco a quelli universitari.

3)
Per tua info io sono un tecnico di sistemi energetici che nella vita si è anche appassionato alla programmazione, l'ho studiata da autodidatta, lavoro presso un'azienda metalmeccanica che usa per il disegno delle sue apparecchiature dei software di disegno vettoriale sviluppati da me, e posso assicurarti che non sono mai andati in crash per colpa di uno StackOverflow.

Passo e chiudo ;-)

PS : ricordati che io nel scrivere un post non ho mai preso in giro nessuno...io rispondo ai post per confrontarmi con gli altri utenti.

1) non è cambiato nulla rispetto al discorso già fatto ... il fatto centrale è l'uso dello stack - 2) non puoi insistere su argomenti che evidentemente ignori - 3) continua a studiarla. Io ci lavoro ogni giorno da più di 30 anni. - nessuno - 19/09/11 16:38
è inutile insistere con una spiegazione approssimativa, appoggiandosi alla giustificazione che essa sia "sufficiente" alla comprensione superficiale dell'argomento. Se si vuole comprendere correttamente la ricorsione bisogna conoscere come avviene la chiamata a funzione, e quindi lo stack. - TheKaneB - 19/09/11 17:13
E soprattutto, se in un forum specifico qualcuno ti dà un'informazione che tu non possiedi e tu sei un autodidatta, prima di "dire e ribadire", con supponenza, che l'interlocutore ha torto, bisognerebbe documentarsi. - nessuno - 19/09/11 17:55
Indicami dove ho scritto che "hai torto"? - mattia1481 - 19/09/11 18:15
accidenti...mi è scappato un punto di domando...auz - mattia1481 - 19/09/11 18:20
punto di domanda - mattia1481 - 19/09/11 18:21
:-) - mattia1481 - 19/09/11 18:22
"Credo proprio di non sbagliare se dico e ribadisco che la ricorsione prescinda dagli "stack" che hai citato poc'anzi. " ... lo hai affermato tu ... e dato che ho affermato la centralità dello stack ... In ogni caso, io termino qui questo thread ... per me è concluso e non mi appassiona più di tanto - nessuno - 19/09/11 18:34
PM