Stavo ancora guardando la ricorsione, mentre procedo col manuale, e facendo girare il programma di elevamento a potenza, mi sono chiesto se si poteva migliorare e come.
Stavo notando che per esempio 2^18=262144 , ma è vero anche che 4^9=262144.
Ora, visto che la ricorsione è pesante in termini di prestazione, non sarebbe meglio ottimizzare?
2^24, lo stack dovrebbe accumulare 24 chiamate, e poi successivamente "srotolarle", peggiorando le prestazioni, mentre invece si potrebbe fare : 256^3.
Io ho scritto un programma, che analizza l'esponente e lo riduce finchè non è dispari, e contemporaneamente, eleva la base al quadrato.
La mia domanda è se quelle righe di codice in più, hanno senso. Detto in breve, se il gioco vale la candela.
Col la ricorsione, io ritengo di si, mentre se fosse stato iterativo, direi proprio di no. Ma qui mi rimando a voi.
Il congelamento nello stack, penso sia abbastanza oneroso, e tra l'altro non illimitato.
Nei microcontrollori (famiglia pic) per esempio i salti tipo call, richiedono 2 cicli di clock, anzichè 1 come altre istruzioni...quindi.
Comunque il programma fa questo:
* analizza e divide l'esponente finchè non diventa dispari
* se è dispari, non fa nulla
insomma provate a dare un occhiata, e magari ho fatto tutto per nulla, ma se non altro rimane una "palestra" di programmazione...
Codice: Seleziona tutto
/*******************************************************************
* Programma ricorsivo elevamento a potenza
* modifiche:
* se abbiamo p.e. 2^12=4096
* si può benissimo fare 16^3=4096
* risparmiando cicli e "pile" nello stack (nel caso di ricorsione
* il programma valuta l'esponende e vede se è divisibile per 2
* se lo è, contemporaneamente la base diventa base^2
******************************************************************/
#include <stdio.h>
#include <stdlib.h>
/*********************************************************
* Funzione ricorsiva
*********************************************************/
unsigned long long int power (unsigned long long int x, int n) {
if (n==0)
return 1;
else
return x*power(x,n-1);
}
/*********************************************************/
int main(void) {
unsigned long long int base;
int exp;
int new_exp;
printf ("base ");
scanf("%llu",&base);
printf ("esponente ");
scanf("%d",&exp);
if (exp%2==0) {
while (1) {
if (exp%2==0) {
new_exp=exp/2;
exp=new_exp;
base=base*base; }
else {
printf ("nuovo esponente %d\n",new_exp);
break;}
}
}
else {
printf ("esponente dispari, non posso ottimizzare nulla, ris= %llu\n",power(base,exp));
return 0;}
printf ("nuovi valori (base,esponente) %llu %d\n", base, new_exp);
printf ("risultato= %llu\n", power(base,new_exp));
return 0;
}
Comunque un debugger dovresti già averlo: gdb
Provalo, è veramente una manna dal cielo! Poi magari ci sarà tempo per utilizzare un IDE sofisticato con un sacco di funzionalità in più rispetto all'accoppiata gedit+gdb, ma se sei all'inizio il debugger non può che aiutarti a capire come avviene il flusso d'esecuzione del tuo codice
) ecc.