[C]Problema con algoritmo ricorsivo.

[Vic_Mackey]

Salve a tutti,non riesco a creare un algoritmo a cui ho pensato quindi non si tratta di un problema relativo ai meccanismi del C ,però attualmente uso questo linguaggio per programmare.Vengo al dunque:

Ho una struttura dati dinamica del tipo linked lista ,doppiamente linkata (così la lista si può scorrere dall'inizio fino alla fine e viceversa) in cui i campi info sono di tipo intero e possono contenere il numero 0 oppure 1,quindi le info della linked lista rappresentano un numero binario,ad esempio :

1<-->1<-->0<-->1

Avevo pensato di sviluppare una funzione RICORSIVA (la versione iterativa è già pronta e funzionante) che mi permettesse di sommare 1 al numero binario che rapressenta la lista; prendendo l'esempio dal numero di sopra e sommandoci 1,si ha :

1<-->1<-->1<-->0
(NB: nel caso in cui il numero ad esempio sia 1<-->1<-->1 ,sommando 1 ovviamente diventa 1<-->0<-->0<-->0).

La cosa importante e che la funzione abbia soltanto due parametri ,ad esempio il prototipo:

void somma_binary(tipo_nodo_lista  inizio_lista,int  r);

Esempio MAIN:

.
.
.
r=1;
somma_binary(inizio_lista,r);
.
.
.

Ho cercato in molti modi di realizzare questo algoritmo ma la difficoltà sta nel fatto che una volta che si arriva alla fine della lista e si somma 1 alla cifra presente nell'ultima posizione,dopo per ritornare all'inizio a ritroso con eventuale resto la cosa diventa complicata.
Grazie in anticipo!

[Scara95]

somma_binary(inizio_lista, r) {
  if (n == 0)
    return;
  if(inizio_lista->left == NULL) {
    inizio_lista->left = allocazione_memoria;
    inizio_lista->left->right = inizio_lista;
    inizio_lista->left->left = NULL;
    inizio_lista->left->info = 0;
  }
  l->info += r & 1;
  if(l->info & 2)
   somma_binary(l->left, 1);
  l->info &= 1;
  somma_binary(l->left, r<<1);
}

Questo dovrebbe funzionare anche se è piuttosto inefficente.
Però puoi sommare solo numeri positivi, e non considera il caso in cui passi all'inizio un NULL, inoltre avrai sempre uno 0 in testa...
Va richiamata con l'ultimo elemento...
E' più semplice implementare una funzione con più parametri e creare una macro che la richiami

[Vic_Mackey]

Originariamente inviato da Scara95

somma_binary(inizio_lista, r) {
  if (n == 0)
    return;
  if(inizio_lista->left == NULL) {
    inizio_lista->left = allocazione_memoria;
    inizio_lista->left->right = inizio_lista;
    inizio_lista->left->left = NULL;
    inizio_lista->left->info = 0;
  }
  l->info += r & 1;
  if(l->info & 2)
   somma_binary(l->left, 1);
  l->info &= 1;
  somma_binary(l->left, r<<1);
}

Questo dovrebbe funzionare anche se è piuttosto inefficente.
Però puoi sommare solo numeri positivi, e non considera il caso in cui passi all'inizio un NULL, inoltre avrai sempre uno 0 in testa...
Va richiamata con l'ultimo elemento...
E' più semplice implementare una funzione con più parametri e creare una macro che la richiami

Ciao,anzitutto grazie per la risposta ed il tempo che ci hai perso però purtroppo è una versione estremamente semplificata e incompleta.Per quanto riguarda i parametri due sono più che sufficienti,ammenochè qualcuno non mi riesca a dimostrare che è impossibile (lo escludo .
Comunque colgo l'occasione andando un attimo OT,essendo un neofita del C ,questo tipo di istruzioni cosa fanno ??

1)l->info += r & 1
2)l->info &= 1;
3)r<<1

Per quanto riguarda l'algoritmo ho provato ad abbozzare qualcosa,ma il problema resta sempre come scorrerre liberamente la lista dall'inizio alla fine e viceversa,non riesco in nessuna maniera xD.

[Scara95]

Scusa, ma hai una versione funzionante della funzione, perchè devi complicarti la vita col scriverne una versione ricorsiva?
Questa è l'unica regola: KISS - Keep It Simple Stupid
Inoltre una funzione ricorsiva (se si vogliono evitare possibili stack overflows) deve godere di alcune proprietà che permettano la tail call optimization, cosa che per altro il C non assicura e che non tutti i compilatori implementano.
Percui non vedo alcun vantaggio nell'implementare questa funzione ricorsivamente, nemmeno la facilità di espressione. Specialmente non vedo vantaggi nell'implementarla con l'obbligo di avere 2 parametri. Torno a dire che puoi facilmente implementare la funzione come vuoi sotto un'altro nome e poi creare una macro con due parametri che la richiami con i parametri giusti.
In ogni caso qui trovi gli operatori che non conosci.

P.s. la ricorsione dovrebbe essere usata quando semplifica le cose, non quando le complica.

[Scara95]

Se non trovi un modo intuitivo con cui scriverlo probabilmente dovresti provare un'approccio diverso. (questo finchè non entrano in gioco le ottimizzazioni, dove di intuitivo c'è poco)

[Vic_Mackey]

Originariamente inviato da Scara95
Scusa, ma hai una versione funzionante della funzione, perchè devi complicarti la vita col scriverne una versione ricorsiva?
Questa è l'unica regola: KISS - Keep It Simple Stupid
Inoltre una funzione ricorsiva (se si vogliono evitare possibili stack overflows) deve godere di alcune proprietà che permettano la tail call optimization, cosa che per altro il C non assicura e che non tutti i compilatori implementano.
Percui non vedo alcun vantaggio nell'implementare questa funzione ricorsivamente, nemmeno la facilità di espressione. Specialmente non vedo vantaggi nell'implementarla con l'obbligo di avere 2 parametri. Torno a dire che puoi facilmente implementare la funzione come vuoi sotto un'altro nome e poi creare una macro con due parametri che la richiami con i parametri giusti.
In ogni caso qui trovi gli operatori che non conosci.

P.s. la ricorsione dovrebbe essere usata quando semplifica le cose, non quando le complica.

Grazie per il link,non mi erano chiare alcune cose
Per quanto riguarda la questione principale del topic hai perfettamente ragione su tutto,infatti mi sto complicando la vita soltanto per esercizio,tuttavia non riesco a trovare ancora nessuna soluzione ricorsiva (quella iterativa è ok).

[Scara95]

Rispondi a questi punti:

• con che cosa richiami la funzione (primo o ultimo elemento)?
• puoi postare la struttura dati completa?
• la somma deve ammettere sia numeri positivi che negativi?

[Vic_Mackey]

Originariamente inviato da Scara95
Rispondi a questi punti:

• con che cosa richiami la funzione (primo o ultimo elemento)?
• puoi postare la struttura dati completa?
• la somma deve ammettere sia numeri positivi che negativi?

1)Si parte dalla testa,però adesso che ci penso se gli passo la lista partendo dall'ultimo elemento si semplifica di parecchio la cosa,ma mi ostino a voler a cercare in tutti i modi per farlo senza alcuna semplificazione.
2)Si,ma in C faccio un passaggio per riferimento all'inizio della testa.
3)Precisamente cosa intendi?Non ricordo molto come funzionava a livello di bit,ad ogni modo la cosa fondamentale è sommare 1 all'ultima cifra e sistemare il resto,per questo ti facevo l'esempio 111 che diventa 1000 (dove si deve aggiungere il nodo contente 1 e farlo diventare nuova testa)

PS:Ho visto che nel post precendente hai utilizzato gli operatori sui bit,purtroppo nei corsi che ho seguito quest'anno nessuno me ne ha parlato,quindi per ora per me restano parecchio segreti.

[Scara95]

Devi sommare solo 1?
non un numero qualsiasi?

[Vic_Mackey]

Originariamente inviato da Vic_Mackey
1)Si parte dalla testa,però adesso che ci penso se gli passo la lista partendo dall'ultimo elemento si semplifica di parecchio la cosa,ma mi ostino a voler a cercare in tutti i modi per farlo senza alcuna semplificazione.
2)Si,ma in C faccio un passaggio per riferimento all'inizio della testa.
3)Precisamente cosa intendi?Non ricordo molto come funzionava a livello di bit,ad ogni modo la cosa fondamentale è sommare 1 all'ultima cifra e sistemare il resto,per questo ti facevo l'esempio 111 che diventa 1000 (dove si deve aggiungere il nodo contente 1 e farlo diventare nuova testa)

PS:Ho visto che nel post precendente hai utilizzato gli operatori sui bit,purtroppo nei corsi che ho seguito quest'anno nessuno me ne ha parlato,quindi per ora per me restano parecchio segreti.

Si esatto ,soltanto 1 all'ultima cifra e sistemare gli eventuali resti.