C/C++ - Funzioni ricorsive, come funzionano?

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..

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:

L2 = elabora(L1,0,L1);

e la funzione elabora è la seguente:

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

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.

Ti consiglio di studiare il concetto di

stack

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

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:

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

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.

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.

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.

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 ?