Ряд Фибоначчи. Подход первый.

Ряд Фибоначчи может быть построен с помощью нехитрой процедуры, в которой два первых элемента равны единице, а последующие равны сумме двух предыдущих:

int fib1(int N)
{
   if(N==1 || N==2)
      return 1;
   else
      return fib(N-1)+fib(N-2);
}

Таким образом мы получаем 1,1,2,3,5,8,13,21,...

Решение задачи построения ряда Фибоначчи при помощи fib1() красиво, но, страшно неэффективно, поскольку наблюдается экспоненциальный рост  числа вызовов при росте N из-за многократных вычислений одних и тех же значений ряда.

                   fib(5)   
                 /        \     
           fib(4)          fib(3)   
         /      \          /     \
     fib(3)      fib(2)   fib(2)  fib(1)
    /     \                

График зависимости времени работы программы вычисления ряда на тестовом компьютере от N показывает, что при относительно небольших номерах, программа "задумывается"


Попробуем немного усовершенствовать процедуру за счёт хранения вычисленных элементов ряда в дополнительном массиве.

#include <stdio.h>
#include <stdlib.h>
#define MAX 100

int fib2(int N)
{
   static int arr[MAX]={1,1};
   if(N==1 || N==2)
     return 1;
   else if(N>MAX)
     exit(1);
   else
     return (arr[N]=(arr[N-1]?arr[N-1]:fib2(N-1))+
                    (arr[N-2]?arr[N-2]:fib2(N-2)));
}

int main()
{
   int i;
   for(i=1;i<=45;i++)
     printf("%d\n",fib2(i));
   return 0;
}

Данная реализация демонстрирует высокую скорость работы, но требует дополнительного массива под промежуточные элементы, сохраняя при этом рекурсивный характер.