محاسبه ی سری فیبوناچی با ارلنگ

حتما شما با سری فیبوناچی در دوران دبیرستان آشنا شده‌اید. بطور اختصار سری فیبوناچی از فرمول زیر بدست می‌آید:

f(n) = f(n-1) + f(n-2)

هر عنصر در این سری حاصل جمع دو عنصر ما قبل است. البته مقدار برای n برابر با صفر و یک هر دو یک است. برای نمونه سری زیر، فیبوناچی است:

1,1,2,3,5,8,13,21

تصور کنید می‌خواهید با استفاده از ارلنگ عنصر n یک سری را محاسبه کنید. اگر بخواهیم فرمول ریاضی آورده شده را به یک برنامه ارلنگ تبدیل کنیم کار سختی در پیش نخواهیم داشت.

-module(fib).
-export([fib/1]).

fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).

خیلی ساده در نمونه کد بالا یک ماژول به اسم fib تعریف شد. تابعی به همین نام نیز تعریف شد که برای مقدار ورودی 0 و 1 خروجی 1 را بر می گردان. برای سایر موارد درست مانند فرمول ریاضی عمل می‌کند. هرگاه تابعی در درون خود خودش را صدا بزند با آن تابع بازگشتی می‌گویند. برای کامپایل کردن کد بالا ابتدا وارد شل ارلنگ شده و کد مربوط را با روش زیر کامپایل و سپس اجرا می‌کنیم:

1>    c(fib.erl).
{ok,fib}

2>    [fib:fib(1), fib:fib(2), fib:fib(3), fib:fib(4), fib:fib(5), fib:fib(6)].
[1,1,2,3,5,8]

خب بنظر کار ما تمام است. اما تابع تعریف شده مشکلاتی دارد. از آنجایی که برای نمونه (fib(n-1) = fib(n-2) + fib(n-3 پس می توان نتیجه گرفت که مقدار(fib(n-2 دوبار محاسبه می‌شود و این مسئله بار زیادی برروی سیستم می‌گذارد.

راه حال بهتر استفاده از نوع خاصی از توابع بازگشتی است که به آنها tail-recursive گفته می‌شود. شاید بهترین ترجمه برای آن بازگشتی انتهایی باشد. در این توابع باز هم خود تابع صدا زده می‌شود اما به عنوان آخرین عبارت و کنترل هرگز به تابع صدا زننده بر نمی‌گردد. با استفاده از این تعریف تابع بصورت زیر باز تعریف می‌شود:

-module(fib2).
-export([fib/1]).

fib(N) -> fib_iter(N, 0, 1).

fib_iter(0, Result, _Next) -> Result;
fib_iter(Iter, Result, Next) when Iter > 0 -> fib_iter(Iter-1, Next, Result+Next).

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

 

timer:tc(fib, fib, [40]). % {556300, 102334155}

timer:tc(fib2,fib,[40]). %{0, 102334155}

مولفه اول در توپل نشان دهنده زمان اجرا بر مبنای میلی ثانیه است. همانطور که می بینید تفاوت فاحش است.

لازم به ذکر است تا کنون JVM و NET. از بازگشتی انتهایی پشتیبانی نمی‌کنند هرچند بنابه گفته مایکروسافت در سال آینده این قابلیت اضافه خواهد شد.