اولین راه‌حلی که می‌توانیم اینجا امتحان کنیم راه‌حل بازگشتی است.

اعداد فیبوناچی طبق تعریف بازگشتی هستند:

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

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // !خیلی کند خواهد بود

…اما برای مقدارهای بزرگ n بسیار کند است. برای مثال، fib(77) ممکن است موتور را به دلیل مصرف تمام منابع پردازنده برای مدتی از کار بیاندازد.

به دلیل اینکه تابع تعداد زیادی زیرفراخوانی ایجاد می‌کند. مقدارهای یکسان دوباره و دوباره ارزیابی می‌شوند.

برای مثال، بیایید یک قسمت از محاسبات را برای fib(5) ببینیم:

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

اینجا می‌توانیم ببینیم که مقدار fib(3) هم برای fib(5) نیاز است و هم برای fib(4). پس fib(3) دو بار به صورت کاملا مستقل فراخوانی خواهد شد.

اینجا درخت بازگشت کامل را داریم:

می‌توانیم به وضوح ببینیم که fib(3) دو بار و fib(2) سه بار ارزیابی می‌شود. کل تعداد محاسبات نسبت به n خیلی سریع‌تر رشد می‌کند و آن را برای n=77 بسیار عظیم می‌کند.

ما می‌توانیم با به خاطر سپردن مقدارهایی که از قبل ارزیابی شده‌اند آن را بهینه کنیم: اگر یک مقدار برای مثال fib(3) یک بار حساب شد، سپس ما می‌توانیم آن را در محاسبات بعدی دوباره استفاده کنیم.

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

به جای اینکه از n به مقدارهای کمتر برویم، می‌توانیم کاری کنیم که حلقه از 1 و 2 شروع کند سپس fib(3) را به عنوان مجموع آنها دریافت کند، سپس fib(4) به عنوان مجموع دو مقدار قبلی، سپس fib(5) و همینطور بالا می‌رود تا به مقدار مورد نیاز برسد. در هر مرحله ما فقط نیاز است که دو مقدار قبلی را به حافظه بسپاریم.

اینجا مراحل الگوریتم جدید را با جزئیات داریم.

شروع:

// a = fib(1) ،b = fib(2) ،این مقدارها طبق تعریف 1 هستند
let a = 1, b = 1;

// را به عنوان مجموع آنها دریافت کن c = fib(3)
let c = a + b;

/* 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)

/* :حالا این دنباله را داریم
   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)

/* :حالا دنباله اینگونه است (یک عدد بیشتر)
      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 از قبل ذخیره شده‌اند.

این روش برنامه نویسی پویا نامیده می‌شود.