[C] Dubbio ricorsione

[GiulioCesare]

Salve ragazzi, premetto che odio la ricorsione, quindi faccio un pò fatica a capirla. Stavo appunto cercando di fare il calcolo della potenza, tramite una funzione ricorsiva, dopo essere spremuto le meningi senza risultati per giorni, ho trovato in rete un'ottima soluzione, ovvero questa:


int pot(int n, int esp)
{

if(!esp)
return 1;

else

return n*pot(n,esp-1);
}


La funzione funziona correttamente, ma non ho capito nel else quando il valore ritornato dalla funzione, viene poi usato per fare il prodotto con la n. La cosa strana è questa, chiamando la funzione pot con i suoi argomenti, come può ritornare un valore, avendo solo semplicemente chiamato la funzione, senza aver fatto nessun calcolo?

[The3DProgrammer]

succede questo: come vedi, la funzione è divisa chiaramente in 2 parti: una con le regole di uscita (if(!exp) return 1) e una con la ricorsione vera e propria: ora, senza scendere troppo nei particolari, supponiamo che tu debba fare 2^3:

l'esecuzione del programma sarà + o meno questa:


passo 1: Chiamata per la prima volta al metodo: quindi pot(2,3). Essendo l'esponente diverso da 0, l'esecuzione prosegue nel ramo else e va a valutare n*pot(n,esp-1). Il passo successivo, quindi, è quello di valutare pot(n,esp-1)

passo 2: esecuzione di pot(n,esp-1), con parametri 2 e 3-1 = 2. Anke qui l'exp è diverso da 0, quindi l'esecuzione prosegue nel ramo else. Si passa quindi a valutare n*pot(n,esp-1)

passo 3: esecuzione di pot(n,esp-1), con parametri 2 e 2-1 = 1. Anke qui l'exp è diverso da 0, quindi l'esecuzione prosegue nel ramo else. Si passa quindi a valutare n*pot(n,esp-1) NB: Ancora nessuna esecuzione di pot è terminata, bensi sono tutte in attesa che si arrivi ad un valore da cui calcolare la soluzione.

passo 4: valutazione di pot(n,esp-1) con n=2 e esp = 0. Questa volta interviene la regola di uscita, che impone il ritorno del valore uno (qualsiasi numero elevato a 0 da appunto 1). A questo punto, tutte le varie chiamate a pot terminano in cascata, con ordine inverso a quello in cui erano iniziate: quindi il procedimento sarà il seguente:

pot(2,0) = 1, quindi l'espressione pot(2,0) del passo 4 è uguale a 1, quindi l'espressione n*pot(2,1) è uguale a 2 (sfrutta il calcolo di pot(2,0)), quella n*pot(2,2) del passo 2 è uguale a 4 e quella del primo passo è pari ad 8. Effettivamente la ricorsione è un po contorta da capire le prime volte, ma è uno strumento molto potente, che consente di esprimere facilmente algoritmi iterativi che risulterebbero molto complessi, ma ha le sue limitazioni;)

ciauz

[GiulioCesare]

Grazie penso di aver capito :D