01: // ricorsione + dynamic programming, prefisso static
02: #include<stdio.h>
03: #include<stdlib.h>
04: 
05: 
06: unsigned long fibonacci(unsigned long n);
07: 
08: int main(int argc, char **argv){
09:   unsigned int n;
10: 
11:   printf("Inserisci l'indice del numero di Fibonacci da calcolare: ");
12:   scanf("%u", &n);
13: 
14:   printf("Il numero di Fibonacci di indice %u vale %lu\n", n, fibonacci(n));
15: 
16: 
17:   return 0;
18: }
19: 
20: #define NGRANDE 2000
21: unsigned long fibonacci(unsigned long n)
22: {
23:   static unsigned long Fibos[NGRANDE]={0,1}; // static rende questa variabile a durata fissa
24: 
25:   printf("DEBUG: sono stata chiamata con n=%ld\n", n);
26: 
27:   if(!n) return 0;
28:   if(Fibos[n]) return Fibos[n]; // se l'ho gia' calcolato inutile ricalcolarlo!
29:   Fibos[n] = fibonacci(n-2)+fibonacci(n-1);
30:   return Fibos[n];
31: }
32: