Telefonino.net network
 
| HOMEPAGE | INDICE FORUM | REGOLAMENTO | ::. NEI PREFERITI .:: | RSS Forum | RSS News | NEWS web | NEWS software |
| PUBBLICITA' | | ARTICOLI | WIN XP | VISTA | WIN 7 | REGISTRI | SOFTWARE | MANUALI | RECENSIONI | LINUX | HUMOR | HARDWARE | DOWNLOAD | | CERCA nel FORUM » |

Torna indietro   WinTricks Forum > Software > Programmazione

Notices

Rispondi
 
Strumenti discussione
Vecchio 09-11-2007, 11.59.01   #1
Downloader
Gold Member
Top Poster
 
Registrato: 04-09-2002
Loc.: Roma
Messaggi: 4.022
Downloader promette bene
[C] Ricorsività

Avrei bisogno di un aiutino per capire al meglio il concetto di ricorsività, visto che questo per me è un argomento davvero ostico in quanto non l'ho mai affrontato.

Vedo che chi usa la ricorsività a meno di grossi problemi da risolvere vede globalmente tutto il problema molto semplicemente e lo risolve con una riga di codice.
Forse (anzi sicuramente) sbaglierò io nell'analizzare quello che una funzione ricorsiva deve fare, ma io per ora anche solo per capire come funziona la ricorsività devo farmi tutte le operazioni e le chiamate che fa lei, e questo oltre ad essere poco una operazione poco agevole e molto lenta non in tutti i casi porta buoni risultati.


Cosa potete dirmi??



tnx!
Downloader non è collegato   Rispondi citando
Vecchio 09-11-2007, 12.18.35   #2
LoryOne
Gold Member
WT Expert
 
Registrato: 09-01-2002
Loc.: None of your business
Messaggi: 5.412
LoryOne ha un'aura spettacolareLoryOne ha un'aura spettacolareLoryOne ha un'aura spettacolare
Quando il risultato di una funzione parametrica diventa il parametro passato alla funzione stessa, tale funzione si dice ricorsiva.
Il calcolo del fattoriale di un numero o la ricerca di sottocartelle di un hard disk sono entrambe funzionalità ricorsive.
E' come dire che una funzione fa ricorso a se stessa un numero x di volte per ottenere il rusltato sperato.
LoryOne non è collegato   Rispondi citando
Vecchio 09-11-2007, 12.26.08   #3
Downloader
Gold Member
Top Poster
 
Registrato: 04-09-2002
Loc.: Roma
Messaggi: 4.022
Downloader promette bene
Il problema che ho a volte studiando dei codici è proprio capire come fa una funzione a restituire un certo valore quando quel valore deve essere sommato ad un'altra funzione ricorsiva.

Poco chiaro eh?

Ecco un esempio che mi sta facendo impazzire:
Codice:
int fibo(int n)
{
 if (n < 2)
  return n;
 else
  return fibo(n-1) + fibo(n-2);
}
Questa funzione come si sarà capito calcola l'nesimo numeri di Fibonacci.
Ma...se iterativamente si risolve facilmente, ricorsivamente invece mi fa fumare il cervello per via dei valori intermedi che le due funzioni ricorsive generano.

Ora siccome credo che sia pazzia per tutti mettersi a calcolare ogni ambiente di funzione che risultato restituisce mi chiedevo se c'era una maniera di riuscire ad arrivare a scrivere il codice in maniera decisamente più veloce senza gli impazzimenti dei calcoli.
Downloader non è collegato   Rispondi citando
Vecchio 09-11-2007, 12.30.07   #4
Thor
Il re di bastoni
Top Poster
 
L'avatar di Thor
 
Registrato: 26-04-2001
Loc.: Milàn
Messaggi: 23.413
Thor promette bene
Se cerchi "ricorsione" su google trovi un sacco di roba
Una funzione ricorsiva, per svolgere il proprio lavoro, richiama sè stessa più volte, aumentando di volta in volta la profondità dell'elaborazione

ad es. il fattoriale, classico

Codice:
#include <stdio.h>

int fattoriale(unsigned int n);

main(void)
{  int n;
   printf("\nIntroduci N:\t");
   scanf("%d",&n);
   printf("\nIl fattoriale di %d è \t%d\n", n, fattoriale(n));
}

int fattoriale(unsigned int n)
{
   if (n==0 || n==1) return 1
   else return n*fattoriale(n-1); /*ricorsione*/
}
se invece lo faccio in versione iterativa, cambia la funzione:

Codice:
int fattoriale(unsigned int n)
{
   int tmp, f=1;
   for (tmp=1; tmp<=n; tmp++)
   f *= tmp;
   return f;
}
___________________________________

Un giorno in cui voleva fare il cattivo, Mister Coniglietto sbirciò oltre la siepe e vide che l'orto del Contadino Fred era pieno di lattuga fresca e verde; Mister Coniglietto, invece, non era pieno di lattuga per niente. E ciò gli parve un'ingiustizia.
Sono un Vampiro! I am a Vampire!

Ultima modifica di Thor : 09-11-2007 alle ore 12.34.44
Thor non è collegato   Rispondi citando
Vecchio 09-11-2007, 12.33.41   #5
Downloader
Gold Member
Top Poster
 
Registrato: 04-09-2002
Loc.: Roma
Messaggi: 4.022
Downloader promette bene
Ho già "googolato", ma non ho trovato una risposta alla mia domanda, o forse l'ho trovata ma non l'ho trovata esauriente, o forse non l'ho capita.

Che una funzione ricorsiva chiami se stessa è chiaro a tutti, non mi è chiaro però come funzionino certi meccanismi ad esempio nel codice che ho postato sopra.
Downloader non è collegato   Rispondi citando
Vecchio 09-11-2007, 12.36.26   #6
Thor
Il re di bastoni
Top Poster
 
L'avatar di Thor
 
Registrato: 26-04-2001
Loc.: Milàn
Messaggi: 23.413
Thor promette bene
be', se chiedi se esista una regola generale per scrivere funzioni ricorsive, la risposta è no..sei tu che tramite astrazione mentale, devi riuscire a tirar fuori un procedimento che può chiamare sè stesso per risolvere il problema.

proprio come per fibonacci. quella è ricorsione non lineare, sono certo che altri tipi di ricorsione, come quello che ho scritto io su, ti vengano più facili, no?
___________________________________

Un giorno in cui voleva fare il cattivo, Mister Coniglietto sbirciò oltre la siepe e vide che l'orto del Contadino Fred era pieno di lattuga fresca e verde; Mister Coniglietto, invece, non era pieno di lattuga per niente. E ciò gli parve un'ingiustizia.
Sono un Vampiro! I am a Vampire!

Ultima modifica di Thor : 09-11-2007 alle ore 12.42.53
Thor non è collegato   Rispondi citando
Vecchio 09-11-2007, 12.41.56   #7
Downloader
Gold Member
Top Poster
 
Registrato: 04-09-2002
Loc.: Roma
Messaggi: 4.022
Downloader promette bene
Quota:
Inviato da Thor
be', se chiedi se esista una regola generale per scrivere funzioni ricorsive, la risposta è no..sei tu che tramite astrazione mentale, devi riuscire a tirar fuori un procedimento che può chiamare sè stesso per risolvere il problema.

proprio come per fibonacci. quella è ricorsione non lineare, sono certo che altri tipi di ricorsione, come quello che ho scritto io su, ti vengano più facili, no?
Infatti, con quelli non ho particolari problemi, perchè comunque sia bene o male riesco ad immaginare quello che devono fare.
Downloader non è collegato   Rispondi citando
Vecchio 09-11-2007, 12.43.16   #8
Thor
Il re di bastoni
Top Poster
 
L'avatar di Thor
 
Registrato: 26-04-2001
Loc.: Milàn
Messaggi: 23.413
Thor promette bene
Comunque sia, la definizione della funzione di fibonacci, se non sbaglio, è proprio:
F0= 0; F1= 1; Fn = F(n-1) + F(n-2), con F0 aggiunto se si vuol far partire la successione con 0.
Dunque proprio la versione "ricorsiva" che si scrive.

http://it.wikipedia.org/wiki/Successione_di_Fibonacci
___________________________________

Un giorno in cui voleva fare il cattivo, Mister Coniglietto sbirciò oltre la siepe e vide che l'orto del Contadino Fred era pieno di lattuga fresca e verde; Mister Coniglietto, invece, non era pieno di lattuga per niente. E ciò gli parve un'ingiustizia.
Sono un Vampiro! I am a Vampire!

Ultima modifica di Thor : 09-11-2007 alle ore 12.47.02
Thor non è collegato   Rispondi citando
Vecchio 09-11-2007, 16.09.00   #9
LoryOne
Gold Member
WT Expert
 
Registrato: 09-01-2002
Loc.: None of your business
Messaggi: 5.412
LoryOne ha un'aura spettacolareLoryOne ha un'aura spettacolareLoryOne ha un'aura spettacolare
Effettivamente è piuttosto difficile riuscire a spiegare il concetto.
Cominciamo dalle cose semplici: il fattoriale di 5 è 120
E' come se l'operazione di moltiplicazione fosse da intendersi in questo modo: 5*4*3*2*1
Si può ottenere lo stesso risultato in questo modo: 5*1*2*3*4
In entrambi i casi, ci si ferma dopo 5-1 volte, cioè dopo 4 moltiplicazioni: 4 è dato infatti da 5-1
Lo scopo principale di una funzione ricorsiva è sapere quante volte è necessario iterare fino a fermarsi; Fermarsi è il punto.
Ogni funzione genera al suo interno una serie di operazioni, ma termina quando il risultato delle operazioni è un numero finito, non il risultato di un' ulteriore operazione algebrica.
Il return a meno che non lo si forzi a restituire 0 si aspetta sempre un valore positivo il più vicino possibile a zero.
Nel nostro caso, n*fattoriale(n-1) si fermerà quando (n-1) sarà uguale a 1
5*(5-1)=20
20*(4-1)=60
60*(3-1)=120
120*(2-1)=120
Sono 4 le operazioni e 2-1=1.
Perdonatemi matematici, ma io sono terra-terra quando spiego. :-(
LoryOne non è collegato   Rispondi citando
Vecchio 09-11-2007, 16.17.46   #10
LoryOne
Gold Member
WT Expert
 
Registrato: 09-01-2002
Loc.: None of your business
Messaggi: 5.412
LoryOne ha un'aura spettacolareLoryOne ha un'aura spettacolareLoryOne ha un'aura spettacolare
Ti faccio notare che anche la funzione iterativa si ferma e tu sai bene quando:
for (tmp=1; tmp<=n; tmp++)
LoryOne non è collegato   Rispondi citando
Rispondi


Utenti attualmente attivi che stanno leggendo questa discussione: 1 (0 utenti e 1 ospiti)
 
Strumenti discussione

Regole di scrittura
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is ON
Gli smilies sono ON
[IMG] è ON
Il codice HTML è OFF

Vai al forum

Discussioni simili
Discussione Autore discussione Forum Risposte Ultimo messaggio
Lo Spammangolo [Dio è grande, ma Sfigatto 'u cugghiunia] Sbavi Chiacchiere in libertà 2015 15-05-2008 09.32.41
Lo Spammangolo[Che lo spam sia con voi] Robbi Chiacchiere in libertà 1971 28-06-2007 09.01.39
oggi è il compleanno di sergio neddi n@ndo Chiacchiere in libertà 36 12-06-2007 00.56.36
Motore di ricerca gratis Downloader Internet e Reti locali 1 29-10-2005 20.58.52

Orario GMT +1. Ora sono le: 07.47.32.


E' vietata la riproduzione, anche solo in parte, di contenuti e grafica.
Copyright © 1999-2017 Edizioni Master S.p.A. p.iva: 02105820787 • Tutti i diritti sono riservati
L'editore NON si assume nessuna responsabilità dei contenuti pubblicati sul forum in quanto redatti direttamente dagli utenti.
Questi ultimi sono responsabili dei contenuti da loro riportati nelle discussioni del forum
Powered by vBulletin - 2010 Copyright © Jelsoft Enterprises Limited.