دنباله فیبوناچی بدون بازگشت

مساله بالا یکی از معروف‌ترین مسایل ریاضی است که در دوران سلطنت امپراطور فردریک دوم مطرح شد. فیبوناچی با حل این مسئله از راه حل فوق دنباله حاصل را به جهان ریاضیات معرفی کرد که خواص شگفت‌انگیز و کاربردهای فراوان آن تا به امروز نه تنها نظر ریاضی‌دانان بلکه دانشمندان بسیاری از رشته‌های دیگر را به خود جلب کرد.

دنباله فیبوناچی در برنامه‌نویسی، یکی از تمرین‌های شایع است که اگر درست نوشته نشود، می‌تواند مقدار زیادی حافظه و پردازنده را هدر دهد. روشی که پیش از هر چیز دیگر به‌ذهن وارد می‌شود، روش زیر است:

I = 1;

J = 1;

Printf(‘%d,%d’, ‘I, J’);

For (k = 1; k « n; k++) {

          Temp = I + J;

          I = J ;

          J = Temp;

          Printf(‘%d’, ‘J’);

}

اما باید توجه کرد که مثلا اگر بخواهیم جمله 200 یک دنباله را بدست بیاوریم، باید از اول شروع به محاسبه کنیم که کمی احمقانه به‌نظر می‌رسد. حساب کردن جمله 200 یک دنباله فیبوناچی، فرمولی ریاضی دارد که یادگرفتن آن بسیار ساده است:

بنابراین کافی است فرمول بالا را به‌صورت شبه‌کد بنویسیم، تا بازدهی بیشتری بدست بیاوریم:

Phi = (1 + SQR(5)) / 2;

(Phi^n – ((1 – phi ) ^ n) ) * SQR(5) / SQR(5) * (Phi^n – ((-1* phi)^(-1*phi)))

تفاوت میان برنامه‌‌نویس خوب و بد، گرفتن نتیجه نیست. هر دو نتیجه را می‌گیرند، اما بازدهی است که تفاوت این دو را مشخص می‌کند.