[C] Funzioni ricorsive

[annigo]

Salve a tutti.
Ho un problema riguardo ad un programma da implementare con funzioni ricorsive in C.

Il testo è il seguente:

Acquisito da tastiera un numero N strettamente positivo, generi e
visualizzi a video (mediante una funzione ricorsiva) tutti i numeri binari di N bit
La generazione dei numeri binari deve essere ottenuta senza eseguire alcuna conversione di valori da decimale a binario.

Non riesco a capire come fare per fare in modo che al primo passo non ci siano bit uguali a uno, al secondo ce ne sia solo uguale a 1, poi due uguali a 1 e cosi via. Oppure viceversa.
Poi bisogna anagrammarli?


Chi sa darmi una mano?
Grazie.

[MdE2005]

Originariamente inviato da annigo
Salve a tutti.
Ho un problema riguardo ad un programma da implementare con funzioni ricorsive in C.

Il testo è il seguente:

Acquisito da tastiera un numero N strettamente positivo, generi e
visualizzi a video (mediante una funzione ricorsiva) tutti i numeri binari di N bit
La generazione dei numeri binari deve essere ottenuta senza eseguire alcuna conversione di valori da decimale a binario.

Non riesco a capire come fare per fare in modo che al primo passo non ci siano bit uguali a uno, al secondo ce ne sia solo uguale a 1, poi due uguali a 1 e cosi via. Oppure viceversa.
Poi bisogna anagrammarli?


Chi sa darmi una mano?
Grazie.

La sezione è sbagliata

Inoltre il forum non è un luogo dove si risolvono esercizi scolastici: posta il codice che hai scritto e spiega in dettaglio ciò che non riesci a fare.


Ciao

[ShaleN]

Hai aperto la stessa discussione due volte: ti ho segnalato al moderatore

[MdE2005]

Ripensandoci forse ho capito cosa intendi, e soprattutto ho deciso di aiutarti dal momento che sei uno studente e che stai facendo i primi passi nel forum. Comunque attenzione, non sarò sempre così benevolo..

Il tuo compito, se ho capito bene, è questo:

es. N = 3 --> 000 001 010 011 100 101 110 111

Se è così questo è il codice ricorsivo: ovviamente sta alla tua *onestà intellettuale* studiarlo a fondo ( , è semplicissimo..) e non limitarli a scopiazzarlo; in caso contrario tutto sarà vano.

#include<iostream>
#include <string>

using namespace std;

void printBit( int num, string binary){
     if ( n==0 ){
          cout << binary << endl;}
     else{
          
          printBit( num-1, binary + "0" );
          printBit( num-1, binary + "1" );
          
          }
}

int main(){
    string binary="";
    int n;
    cin >> num;
    printBit(num, binary);
    system("pause");
    return 0;
}

Ciao

[GliderKite]

Quoto il primo messaggio di IBM aggiungendo che il Politecnico fa male...

In C....

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


void recursive( unsigned * const vect, const unsigned size, const unsigned pos );

int main()
{
	const unsigned size = 3;

	unsigned *v = (unsigned *) malloc( size * sizeof(unsigned) );

	recursive( v, size, 0 );

	free( v );

	getc( stdin );
	return 0;
}


void recursive( unsigned * const vect, const unsigned size, const unsigned pos )
{
	int i;

	if( pos == size )
	{
		for( i = 0; i != size; ++i )
			printf( "%u", vect[ i ] );

		putchar( '\n' );

		return;
	}

	vect[ pos ] = 0;
	recursive( vect, size, pos+1 );

	vect[ pos ] = 1;
	recursive( vect, size, pos+1 );
}

[annigo]

Chiedo scusa per tutte le mie mancanze!
Sono nuovo del formu, vedrò di adattarmi al più presto alle regole.


Non mi è chiaro ancora questo passaggio.

vect[ pos ] = 0;
	recursive( vect, size, pos+1 );

	vect[ pos ] = 1;
	recursive( vect, size, pos+1 );

Me lo puoi spiegare, per cortesia?
Non riesco a capire come la funzione sistema gli 0 e gli 1 nei vari modi.

Grazie ancora.

[GliderKite]

Per capire quel pezzo di codice, che sta alla base di tutto l'esercizio, devi tenere a mente essenzialmente due cose:

1) Una procedura ricorsiva ricorre ad un algoritmo che si esprime in termini di se stesso, cioè lavora su dati che riducono il problema da risolvere in un sottoproblema più semplice da affrontare.

2) Una funziona chiamata dal chiamante torna a questo una volta completata la sua esecuzione, quindi una volta risolto il sottoproblema più semplice il risultato dell'operazione viene tornato al chiamante.

In particolare nel caso in questione la prima recursive() viene chiamata subito dopo aver posizionato uno 0 nella elemento del vettore pos-esimo (che aumenta di una unità per ogni chiamata fino a raggiungere la condizione di terminazione, cioè una volta sistemati tutti gli elementi del vettore la funzione stampa il vettore e torna al chiamante). E segue quindi la seconda recursive() che opera nello stesso modo, dopo aver però posizionato il valore 1 nell'elemento pos-esimo.

Ovviamente il discorso è espresso in parole povere, un consiglio: oltre a ampliare le tue basi su questi argomenti se desideri avere subito maggior chiarezza utilizza un debugger e prendi in considerazione lo stack delle chiamate e il relativo valore di pos per ogni chiamata.

[annigo]

Stavo giusto usando un debugger.
Ma proprio non capisco alcune cose.

Nel caso in cui size=3.
La prima recursive() viene eseguita 3 volte posizionando tre 0.
Si ha dunque la condizione di terminazione size=pos, quindi la stampa.
Poi quando esce dal ciclo di stampa perchè passa alla seconda recursive() e non alla prima?
E il pos da 3 ritorna 2!...come mai?

Chiedo scusa per la mia ignoranza ma non ci arrivo proprio!

[GliderKite]

Originariamente inviato da annigo
Stavo giusto usando un debugger.
Ma proprio non capisco alcune cose.

Nel caso in cui size=3.
La prima recursive() viene eseguita 3 volte posizionando tre 0.
Si ha dunque la condizione di terminazione size=pos, quindi la stampa.
Poi quando esce dal ciclo di stampa perchè passa alla seconda recursive() e non alla prima?
E il pos da 3 ritorna 2!...come mai?

Chiedo scusa per la mia ignoranza ma non ci arrivo proprio!

Dopo che viene stampato l'output la funzione ritorna al chiamante giusto?

Chi l'ha chiamata la funzione che ha stampato i 3 zeri? Quali erano i parametri con cui era stata chiamata, ed in particolare quanto valeva pos prima che venisse chiamata?

[OT]: Evita frasi del tipo: "Chiedo scusa per la mia ignoranza ma non ci arrivo proprio!"

[annigo]

ok, osservando la struttura del problema e facendo il debug del tuo programma mi sembra di avere capito!..

In pratica ogni volta ritorna ai livelli precedenti.
Come inception!


Grazie mille per la pazienza e i consigli.