Soulcyber (Normal User)
Newbie
Messaggi: 1
Iscritto: 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++ |
truct Cella { int valore; struct Cella *next; } 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 |
e la funzione elabora è la seguente:
Codice sorgente - presumibilmente C++ |
Lista elabora (Lista LL, int f, Lista tt) { Lista aux; If (LL == NULL) return NULL; If (f) { aux = elabora(LL->next,(f+1)%2,tt); LL->next = aux; return LL; } else { aux = elabora(LL->next,(f+1)%2,LL); if (tt != LL) tt->next = LL; return aux; } }
|
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 |
|
nessuno (Normal User)
Guru^2
Messaggi: 6380
Iscritto: 03/01/2010
|
Ti consiglio di studiare il concetto di
stack
(e non mi dire che lo conosci bene perché non avresti questi dubbi sulle funzioni ricorsive)
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à. |
|
gigisoft (Member)
Guru
Messaggi: 696
Iscritto: 11/10/2008
|
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++ |
int Factor(int N) { // Controllo se l'ordine del problema e' // sufficientemente basso per risolverlo if ((N == 0) || (N == 1)) { return 1; // Se e' cosi' lo risolvo banalmente } else { return N * Factor(N - 1) // Altrimenti provo a ridurlo a un ordine piu' basso } }
|
Ragiona in questo senso, dovrebbe riuscirti piu' facile capire.
Ciao.
Luigi
Ultima modifica effettuata da gigisoft il 19/09/2011 alle 14:26 |
|
Ultimo (Member)
Guru
Messaggi: 877
Iscritto: 22/05/2010
|
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 ?
If ok Then GOTO Avanza else GOTO Inizia
|
|
nessuno (Normal User)
Guru^2
Messaggi: 6380
Iscritto: 03/01/2010
|
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
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à. |
|
mattia1481 (Member)
Pro
Messaggi: 84
Iscritto: 03/11/2008
|
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.
|
|
mattia1481 (Member)
Pro
Messaggi: 84
Iscritto: 03/11/2008
|
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.
|
|
mattia1481 (Member)
Pro
Messaggi: 84
Iscritto: 03/11/2008
|
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 (Member)
Pro
Messaggi: 84
Iscritto: 03/11/2008
|
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.
|
|