Problema ricorsione

di
enricoscarsissimo
il
9 risposte
E
enricoscarsissimo
Utente Attivo
Iscritto da
dic, 2018
Messaggi:
79

Problema ricorsione

Ciao ragazzi, sono uno studente disperato alle prese con il linguaggio C. Sto cercando di capire la ricorsione, e non vengo a capo di un problema che dovrebbe essere molto semplice. L'esercizio consiste nello scrivere la somma attraverso il concetto di successivo usato ricorsivamente. In particolare non capisco perchè restituisca il valore corretto nonostante il codice manchi di un punto fisso. Vi posto il codice: 
#include <stdio.h>
int suc(int x){
	return ++x;
}

int somma(int a, int b){
	if (b>0)
		return somma(suc(a), b-1);
}

int main(){
	int x;
	x = somma(3,2);
	printf("%d",x);
}
Da quello che so l'ultima chiamata della funzione somma (quando b=0) non facendo nulla dovrebbe restituire "1", e nelle return successive non dovrebbe succedere nulla se non appunto restituire 1 alla fine. Invece nella stampa restituisce correttamente il valore della somma. Qualcuno sa spiegarmi il perchè?
Un codice più sensato dovrebbe essere: 
int addiz(int a, int b) {
//	if(b==0)	
//		return a;
  	if(b>0){
  		return addiz(suc(a),b-1);
Eppure come detto funziona in entrambi i casi (tranne nel caso b=0 ma non è quello il punto della questione). Spero si sia capito qualcosa, grazie mille in anticipo se ci sarà un'anima pia che mi risponderà

9 Risposte

  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6011

    Re: Problema ricorsione

    Ecco un esempio di codice CHE FUNZIONA PER SBAGLIO
    Da quello che so l'ultima chiamata della funzione somma (quando b=0) non facendo nulla dovrebbe restituire "1"
    Sai MOOOOLTO MALE

    MAI FIDARTI di quello che sai, perche' DI SICURO non lo sai

    Usa SEMPRE nomi di funzioni COMPRENSIBILI, il che vuol dire SEMPRE parole complete di senso compiuto.
    Non e' questo il momento di pensare alle ottimizzazioni (se la funzione ha un nome piu' breve il mio codice viene eseguito piu' velocemente: BALLE )

    Se usi "suc" ("successivo" ) allora usa anche "prec" ("precedente") e NON "b-1"

    Ogni FUNZIONE DEVE SEMPRE (ma SEMPRE SEMPRE, fino alla fine del tempo )) uscire mediante un return.

    TU NON SAI (e non puoi saperlo, ma non lo sa nemmeno uno che ha N-milioni di anni di esperienza) che cosa la funzione puo' ritornare SE NON ESCE DA UN RETURN in cui c'e' ESPLICITAMENTE DETTO che cosa deve ritornare.

    QUINDI, riassumento,

    1) il primo codice che hai postato E' TOTALMENTE CANNATO ANCHE SE SEMBRA, per un'improbabile volonta' divina, funzionare. FUNZIONA PER UN CUL...O GRANDE COME L'INTERO PIANETA

    2) il secondo codice, ha un che di giusto, MA MANCANO PEZZI FONDAMENTALI

    Idea buona, implementazione sbagliata


    RICORDA:

    CI DEVE ESSERE SEMPRE la base della ricorsione, e ad ogni chiamata ricorsiva il lavoro di fare DEVE ESSERE MENO di quello DEL PASSO PRECEDENTE.


    Ritenta, sarai piu' fortunato la prossima volta
  • E
    enricoscarsissimo
    Utente Attivo
    Iscritto da
    dic, 2018
    Messaggi:
    79

    Re: Problema ricorsione

    Grazie mille della risposta, stavo impazzendo dietro a questa storia, tutto potevo pensare meno che fosse una coincidenza, credevo mi fossi perso chissà quale passaggio. Adesso torno a studiare, nel caso di ulteriori problemi posto qui. Ancora grazie
  • E
    enricoscarsissimo
    Utente Attivo
    Iscritto da
    dic, 2018
    Messaggi:
    79

    Re: Problema ricorsione

    Già che ci sono sfrutto la tua gentilezza e posto un altro problema sulla ricorsione che mi preme. In questo caso il codice funziona, solo credo sia scritto molto male, utilizzando un trucchetto che penso faccia perdere di senso il concetto stesso di ricorsione, vorrei solo sapere se secondo te ha senso un programma del genere o è meglio riformularlo da capo con una chiave di lettura un po' diversa.
    Il codice è il seguente: 
    #include <stdio.h>
void efferic(int);
int main(){				//esempi: 
	int n = 3	;			//  n=3  -->  333221.122333
	efferic(n);				//n=4 --> 4444333221.122333444 ecc ecc
}


void efferic(int n){
	int i;
	static int sign = 0;
	static int n2 = n;
	if(n==1)	{
		printf("1.1");
		sign = 1;
	}
	else
		for(i=0; i<n; i++)
			printf("%d",n);

	if(n2==n && sign == 1)
		return;
			
	if(!sign)	
		return efferic(n-1);
	else if(sign)
		return efferic(n+1);
}
    . Ora il mio problema in questo caso era tenere traccia di dove fossi arrivato, cosa che in ricorsione non mi è chiaro come fare. Per farlo sfrutto le variabili static, cosa che ad essere sincero non ho mai visto fare al mio prof. Nel testo dell'esercizio suggeriva di "NON alterare i prototipi! Se, tuttavia, si sentisse l’esigenza di ulteriori parametri nella ricorsione… si può naturalmente ricorrere a funzioni ausiliarie («mascherando» la loro invocazione)" Ovviamente non ho la più pallida idea di cosa stia parlando
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1241

    Re: Problema ricorsione

    Mi sembra strano che quel codice compila:
    - premesso che ritornare una funzione void non ha molto senso, ti faccio presente che il compilatore me lo segnala come errore dicendo che lo standard C vieta di ritornare un'espressione in una funzione di tipo void;
    - le variabili statiche devono essere inizializzate con una costante.

    In ogni caso la tua funzione per n=5 viene richiamata 9 volte e non 5 come invece sarebbe lecito aspettarsi. Del resto mi sembra che ti sia reso conto da solo che non stai utilizzando a pieno il concetto di ricorsione.
    Provo a darti un input... una chiamata ricorsiva può essere preceduta e seguita da varie istruzioni; le istruzioni precedenti vengono eseguite nello stesso ordine in cui vengono effettuate le varie chiamata, mentre quelle successive vengono eseguite a ritroso!
  • E
    enricoscarsissimo
    Utente Attivo
    Iscritto da
    dic, 2018
    Messaggi:
    79

    Re: Problema ricorsione

    Allora, innanzitutto grazie del consiglio, mi sono un po' scervellato e sono arrivato alla seguente soluzione: 
    #include <stdio.h>
void efferic(int);
int main(){
	int n = 3  	;			//   -->  333221.122333
	efferic(n);
}


void efferic(int n){
	int i;
	if(n==1)
		printf("1.");
	else{
		 for (i=0; i<n; i++)
			printf("%d",n);
		 efferic(n-1);
		}

	for(i=0; i<n; i++)
		printf("%d",n);
	
	
	
}
    Che credo sia simile a quella che immaginavi tu.
    Adesso però stavo cercando di scrivere un codice analogo per generare una sequenza del tipo (per n=3) --> 11122322111
    Purtroppo proprio non riesco a trovare un metodo per ricordarmi sia il numero di stampe da effettuare sia il numero che effettivamente voglio stampare,se avete qualche suggerimento è ben gradito (possibilmente che non aggiunga una variabile static )
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1241

    Re: Problema ricorsione

    Allora, innanzitutto grazie del consiglio, mi sono un po' scervellato e sono arrivato alla seguente soluzione:
    ...
    Che credo sia simile a quella che immaginavi tu.
    Va bene, o ancora più semplicemente: 
    void f(int n)
{
    int i;
    for(i = 0; i < n; ++i)
    {
        printf("%d", n);
    }
    if(n > 1)
    {
        f(n - 1);
    }
    else
    {
        printf(".");
    }
    for(i = 0; i < n; ++i)
    {
        printf("%d", n);
    }
}
    Per quanto riguarda il nuovo esercizio la funzione deve essere sempre del tipo void f(int n)?
  • E
    enricoscarsissimo
    Utente Attivo
    Iscritto da
    dic, 2018
    Messaggi:
    79

    Re: Problema ricorsione

    Si in effetti è più "pulito", thanks
    Esatto l'altro esercizio dev'essere ancora void f(int), ti riscrivo però il suggerimento del prof, io non ho proprio capito cosa intendesse:

    NON si devono alterare i prototipi! Se, tuttavia, si sentisse l’esigenza di ulteriori
    parametri nella ricorsione… si può naturalmente ricorrere a funzioni ausiliarie
    («mascherando» la loro invocazione)

    In particolare non capisco cosa intenda dire con quel "mascherare" l'invocazione, ma a prescindere da ciò proprio non riesco a immaginare come una chiamata di funzione possa aiutarmi a tenere traccia di qualche valore, visto che ad ogni chiamata di ricorsione i parametri che gli posso passare cambiano in continuazione
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1241

    Re: Problema ricorsione

    In effetti neanche io ho ben capito cosa intenda il tuo prof!
  • E
    enricoscarsissimo
    Utente Attivo
    Iscritto da
    dic, 2018
    Messaggi:
    79

    Re: Problema ricorsione

    Se siete curiosi vi posto la soluzione del prof
    
void effetre( int n ) {
  F3(n,n);
}
void F3(int n, int k) {
  int t;
  if( n == 1 ) {
    printf("%d", k);
    return;
  }
  for( t=0; t<n; t++ )  /* Fase "montante" */
    printf("%d", k-n+1);
  F3( n-1, k);
  for( t=0; t<n; t++ )  /* Fase "calante" */
    printf("%d", k-n+1);

}
Devi accedere o registrarti per scrivere nel forum
9 risposte