الحل الأول الذي مكن تجربته هنا هو الحل المتكرر.

أعداد فيبوناتشي متكررة وذلك واضح من التعريف:

function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // will be extremely slow!

لكن القيم الكبيرة من الـ n سيكون بطئ جداً مثلاً fib(77) يمكن أن تعطل المحركلمد من الزمن

ذلك لأن الدالة تحتوي علي منادايات كثيرة جداً داخلها لنفسها. نفس القيم تحسب مراتٍ كثيرة.

مثلاً لنري قطعة من حساب fib(5):

...
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
...

fib(5) و fib(4) كلاهما يحتاج لحساب fib(3) إذن هذا الدالة سوف تنادي مراتان ليس لهما علاقة ببعضهما.

ها هي صورة كاملة لشجرة التكرار:

واضح هنا أن fib(3) تمت مناداتها مرتين و fib(2) سيتم مناداتها وتنفيذها ثلاث مرات. لذلك سيكون عدد الدوال التي تم تنفيذها سيكون هائل جداً حتي إذا كان n=77.

يمكننا تحسين هذا عن طريق تذكر القيم التي تم حسابها من قبل: مثلاإذا وجدنا fib(3) تم حسابها من قبل نأتي بقيمتها فوراً ولا نقوم بتنفيذها مرة أخري

ذلك يضع أمامنا خيار أخر وهو أن نتخلي عن التكرار واستخدام طريقة حل مبنية علي الـ Array مختلفة تماماً

بدلاً من أن نذهب من n أسفل للقيم الأقل, يمكن أن نصنع حلقة تبدأ من 1 و 2, ثم نأتي بـ fib(3) بأعتبار أن ناتجها هو مجموعهم, ثم fib(4) بأعتبار أن ناتجها مجموع القيماتان السابقان ثم fib(5) تذهب لأعلي ثم أعلي حتي تصل إلي القيمة المطلوبة. كل ما نحتاج تذكره هو الرقمين السابقين.

هنا سنشرح الخطوات للخوارزمية الجديدة بالتفصيل.

في البداية:

// a = fib(1), b = fib(2), these values are by definition 1
let a = 1, b = 1;

// get c = fib(3) as their sum
let c = a + b;

/* we now have fib(1), fib(2), fib(3)
a  b  c
1, 1, 2
*/

الأن نحن نريد الحصول علي fib(4) = fib(2) + fib(3).

الأن نحتاج إلي تبديل المتغيرات a,b سيصبحوا fib(2),fib(3) و c سيكون مجموعهم :

a = b; // now a = fib(2)
b = c; // now b = fib(3)
c = a + b; // c = fib(4)

/* now we have the sequence:
   a  b  c
1, 1, 2, 3
*/

الخطوة التالية تعطينا تسلسل أخر للأرقام:

a = b; // now a = fib(3)
b = c; // now b = fib(4)
c = a + b; // c = fib(5)

/* now the sequence is (one more number):
      a  b  c
1, 1, 2, 3, 5
*/

وهكذا وهكذا حتي نحصل علي القيمة المطلوبة. هذا أسرع بكثيير ويمنع حساب شئ تم حسابه مسبقاً.

الكود كاملاً:

function fib(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

الحلقة تبدأ من i=3, لأننا نعرف قيمة العددين الأولين a=1, b=1.

هذا الحل يسمي البرمجة الديناميكية.