[C/C++] Ricorsione

[LoneFellow]

Salve a tutti ,
La ricorsione sta nel scrivere , in ordine crescente i numeri da 0 a N in binario, tutto quanto tramite una ricorsione . Il problema è risolto , solo che si capisce che una volta arrivato alla fine del vettore , si passa all elemento successivo portandolo a uno ed il resto tra il elemento attuale ed N viene messo a " 0 " dopo di che successivamente settato con " 1 " da N verso il elemento attuale e cosi via . Quello che non capisce è come fa a decrescere " i " e come fa ad uscire dalla ricorsione una volta stampato l ultimo numero.

La funzione sarebbe questa :

void binary(int i, int *vet, int n)
{
  int j;

  if (i >= n) {
    for (j=0; j<n; j++) {
      printf("%d", vet[j]);
    }
    printf("\n");
    return;
  }

  vet[i] = 0;
  binary(i+1, vet, n);

  vet[i] = 1;
  binary(i+1, vet, n);
}

[LoneFellow]

Intricata? Di funzionare funziona ... Guarda l intero codice è questo..

#include <stdio.h>
#include <stdlib.h>

void binary(int i, int *vet, int n);

int main(void)
{
  int n, *vet;

  printf("Numero di bit: ");
  scanf("%d", &n);

  vet = (int *)malloc(n * sizeof(int));
  if (vet == NULL) {
    printf("Errore di allocazione.\n");
    exit(1);
  }
  printf("Numeri Binari\n");
  binary(0, vet, n);
  free(vet);

  //system("pause");
  return 0;
}

void binary(int i, int *vet, int n)
{
  int j;

  if (i >= n) {
    for (j=0; j<n; j++) {
      printf("%d", vet[j]);
    }
    printf("\n");
    return;
  }

  vet[i] = 0;
  binary(i+1, vet, n);

  vet[i] = 1;
  binary(i+1, vet, n);
}

[LoneFellow]

Mi scuso mi sono spiegato male, il codice è funzionale al 100% , vorrei solo sapere come fa a decrescere "i" e come fa a stabilire la fine della ricorsione. Perchè guardando il codice non riesco a capirlo. Mentre quel "return" piazzato la in mezzo all' iterazione

[banryu79]

Data la funzione ricorsiva:

void binary(int i, int *vet, int n)
{
    int j;
    if (i >= n) {
        for (j=0; j<n; j++) {
            printf("%d", vet[j]);
        }
        printf("\n");
        return;
    }

    vet[i] = 0;
    binary(i+1, vet, n);

    vet[i] = 1;
    binary(i+1, vet, n);
}

Abbiamo che il caso base (quello in cui la ricorsione termina) è la parte evidenziata in sienna (l'ultima istruzione del blocco è appunto un return).
Nota infatti che è un blocco if. La condizione di uscita è appunto i >= n, quindi la ricorsione termina quando la variabile "i" assume un valore maggiore o uguale alla variabile "n".

I valori iniziali delle variabili "i" e "n" sono determinati dal chiamante che li passa alla funzione, dopodiche "n" rimane costante per tutta la durata delle chiamate ricorsive mentre si vede che "i" viene incremetntata (non decrementata) ad ogni chiamata ricorsiva, l'ho evidenziato in oliva

[LoneFellow]

Originariamente inviato da banryu79

Data la funzione ricorsiva:

void binary(int i, int *vet, int n)
{
    int j;
    if (i >= n) {
        for (j=0; j<n; j++) {
            printf("%d", vet[j]);
        }
        printf("\n");
        return;
    }

    vet[i] = 0;
    binary(i+1, vet, n);

    vet[i] = 1;
    binary(i+1, vet, n);
}

Abbiamo che il caso base (quello in cui la ricorsione termina) è la parte evidenziata in sienna (l'ultima istruzione del blocco è appunto un return).
Nota infatti che è un blocco if. La condizione di uscita è appunto i >= n, quindi la ricorsione termina quando la variabile "i" assume un valore maggiore o uguale alla variabile "n".

I valori iniziali delle variabili "i" e "n" sono determinati dal chiamante che li passa alla funzione, dopodiche "n" rimane costante per tutta la durata delle chiamate ricorsive mentre si vede che "i" viene incremetntata (non decrementata) ad ogni chiamata ricorsiva, l'ho evidenziato in oliva

Quell iterazione viene usata solamente per stampare il vettore , dopo di che il return salta alla seconda chiamata della funzione ..
Se provi a guardarlo con un debug vedrai. Poi ogni volta che passa il return e fa la chiamata alla funzione decrementa .. Per quello dicevo che mi pare strano, come fa " i " a decrementare .

[banryu79]

Originariamente inviato da LoneFellow

Poi ogni volta che passa il return e fa la chiamata alla funzione decrementa .. Per quello dicevo che mi pare strano, come fa " i " a decrementare .

Ops... ho letto il codice in fretta, e ora che me lo fai notare hai ragione.
Infatti prova a simulare cosa succede se chiami la funzione con i che vale 1 e n che vale 2...
La variabile i non viene mai decrementata, credo che a un certo punto si vada a scrivere fuori dell'array... se ti ha fuzionato è stata una questione di culo.

Fai prima a scrivertene una nuova tu, magari con un approccio diverso (ad esempio l'operazione di stampa dell'array non ha niente a che vedere con la creazione dell'array stesso, la lascierei fuori della funzione). Prima butta giù l'algoritmo in pseudocodice, come ha fatto Antonio23, poi lo implementi.

[LoneFellow]

Originariamente inviato da banryu79

se ti ha fuzionato è stata una questione di culo.

Fai prima a scrivertene una nuova tu, magari con un approccio diverso (ad esempio l'operazione di stampa dell'array non ha niente a che vedere con la creazione dell'array stesso, la lascierei fuori della funzione). Prima butta giù l'algoritmo in pseudocodice, come ha fatto Antonio23, poi lo implementi.

La funzione genera tutti i numeri di n bit , n viene acquisito , 2 bit genera i numeri 00 01 10 11 , 3 bit generea 000 001 010 011 100 101 111 etc .. E infatti il codice è leggibile per me solo a un certo punto , il concetto della ricorsione l ho capito ma non ho capito come ha fatto ad implementarlo, se noti partendo dall posizione 2 lui azzerra poi riempie di uno, ed uno alla volta stampa, arrivato alla posizione di 1 lui la prossima la mette a 1 che era 0, azzerra tutto di nuovo eccetto la nuova posizione, e dopo dalla coda del vettore riempie di uno e stampa ogni volta che inizializa una posizione. Non è culo, non capisco come caspita fa quella i ad incrementare, visto che non è una meccanica esplicita ...

[wingman87]

A me la funzione sembra giusta... dov'è l'errore?
Se con un breakpoint ti posizioni all'interno dell'if è normale che vedrai i decrementare perché dopo il return tornerai alla funzione chiamante dove i non vale più i+1 ma solo i.
Tra l'altro questa soluzione non sarà elegante e leggibile però è interessante.

[wingman87]

Ho provato a fare un disegnino...

Questo bellissimo disegno vorrebbe rappresentare sotto forma di albero le chiamate ricorsive per n=3.
Su ogni nodo ho segnato uno zero o un uno, se ci fai caso tutti i rami di sinistra hanno zero, tutti quelli di destra uno. I rami di sinistra rappresentano la prima chiamata ricorsiva, i rami di destra la seconda. Il numero 0 o 1 è quello che viene scritto in vet[i] prima della chiamata.
Quando i=n, in questo caso quando i=3, il ciclo stampa i valori di vet[0], vet[1] e vet[2], cioè i valori sul cammino dalla radice alla foglia.
A me sembra carina come soluzione...

[LoneFellow]

Originariamente inviato da wingman87

A me la funzione sembra giusta... dov'è l'errore?
Se con un breakpoint ti posizioni all'interno dell'if è normale che vedrai i decrementare perché dopo il return tornerai alla funzione chiamante dove i non vale più i+1 ma solo i.
Tra l'altro questa soluzione non sarà elegante e leggibile però è interessante.

Ho provato, ho messo dei break point su tutta la funzione solo che il decremento lo mostra mentre il cursore del break point è sulla parentesi di chiusura . Cosi non essendo una chiamata di riferimento il valore non viene sovrascritto. Bene questo una volta ma se capita più volte di fila ? Vuoi dire forse che io percorgo un cammino diverso partendo sempre dalla radice, e ogni volta che finisco ritorno indietro al valore iniziale, ma essendo che sono ancora nella funzione iniziale mi rimane solo il incremento iniziale ? Cosi i decrementi che mi mostra sulla parentesi grafe sarebbe il percorso al ritroso della chiamata?

[wingman87]

Esatto, prendi ad esempio il cammino 011 del disegnino che ho fatto prima: prima di passare al valore successivo (100) vedrai decrementarsi i 3 volte. In realtà non è che i si decrementa, semplicemente i non è mai cambiata. Devi immaginare che le diverse chiamate a funzione si impilano una sull'altra, ognuna con i propri parametri. Quando la funzione in cima alla pila giunge all'istruzione return, essa si "estrae" dalla pila e l'esecuzione riparte dov'era rimasta nella funzione immediatamente sotto.

[LoneFellow]

Capito, alla fine bastava cambiare ottica
Grazie .

[LoneFellow]

Un ultima domanda , visto che le funzioni sono concatenate, c è un modo per poterle rintraciare con il debug? Che già adesso con un problema semplice come questa con n 3 sono 12 chiamate ..
Comunque, è come se dopo la chiamata dopo che inizializa a 1 avesse un return perciò ritorna alla precedente , penso sia implicito, anche perchè dopo di lei il codice finisce..