ֆիբոնաչիի թվեր

[shgalex]

ֆիբոնաչիի ֆունկցիան սահմանվում է հետևյալ կերպ


f(n) = 1 if n = 0;
f(n) = 1 if n = 1;
f(n) = f(n-1) + f(n-2);

հեշտ խնդիր

տալ անրադարձ(ռեկուրսիվ) առնչություն, որով կհաշվվի ֆիբ. թվերը բոլոր n - երի համար, ընդ որում ալգորիթմի բարդությունը լինի O(n) (ո կարգի)

Իսկ՞ այսպես կստացվի:

size_t  fibonacci(size_t n){
   size_t  fibi, fib1 = 1, fib2 = 1; int j = 2;
      if(n > 2){
               for(int i = 2; i < n; i++){
                       fibi = fib1 + fib2;
	  fib2 = fib1; fib1 = fibi;}
                         }
	else if(n == 1) return fib1;
	else if(n == 2) return fib2;
return fibi;}

Ներեղություն , ես անրադարձ բարը չեի նկատել: