Fibbonacijevo zaporedje

Tudi člen Fibbonacijevega zaporedja izračunamo s pomočjo rekurzije. Obrazec je .

#include<stdio.h>
long Fib(int b);     /*prototip*/

void main(void) {
  int n;
  printf("Katero Fibbonacijevo število naj računa:\n");
  scanf("%d", &n);
  printf("%d-ti člen je %ld \n", n, Fib(n));
} /* main /*

long Fib(int n) {
  return (n<=2? 1: Fib(n-1) + Fib(n-2)
} /* Fib */

členi so: 1, 1, 2, 3, 5, 8, ... . Če vzamemo za n=35 računa zelo dolgo, ker je treba najprej izračunati za n=34 in n=33. Pri n=34 je potrebno izračunani za n=33 in n=32. Potem pa še na drugi strani za n=33 je potrebno izračunati za n=32 in n=31. To traja tako dolgo dokler ne računamo pri n=3, n=2 in n=1.

Kako izračunati n-ti člen FIB zaporedja hitreje?