۸ - ۴اعداد فیبوناچی

تایپ‌ها

اولین چیزی که باید در نظر بگیریم، تایپ سیگنچر ِ ممکن برای تابع‌مونه. سری فیبوناچی فقط شامل اعدادِ کامل و مثبت میشه. آرگومان تابع هم همینطور، چون می‌خوایم n-اُمین عدد فیبوناچی رو برگردونه. جواب تابع هم یه عدد کامل و مثبت میشه، چون یه عدد فیبوناچی‌ه. پس با ‏‎Int‎‏ یا ‏‎Integer‎‏ کار داریم. میشه از یکی از این دو تایپِ معین، یا از یه تایپکلاس برای پلی‌مورفیسم محدود استفاده کنیم. نهایتاً یه تایپ سیگنچر ای می‌خوایم که یک آرگومان صحیح بگیره و یک آرگومانِ صحیح برگردونه، چیزی شبیه این:

fibonacci :: Integer -> Integer
-- یا
fibonacci :: Integral a => a -> a

فرمان پایه

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

ولی اعداد فیبوناچی یه کم پیچیده‌تر اند، چون دو تا فرمان پایه لازم دارن. چون محاسبه‌ی عدد بعدی دو عدد لازم داره، سری اعداد هم باید با دو تا عدد شروع بشن. عددِ بعد از صفر میشه یک، و ما هم برای شروعِ اعداد، صفر رو با ۱ جمع می‌کنیم. در نتیجه این دو عدد میشن فرمان‌های پایه برای تابع:

Fibonacci  :: Integral a => a -> a
fibonacci 0 = 0
fibonacci 1 = 1

آرگومان‌ها

تا اینجا مشخص کردیم آرگومانی که تابع بهش اعمال میشه یه عددِ صحیح ِه، و اون عضوی از اعداد فیبوناچی رو نشون میده که می‌خوایم پیدا کنیم. یعنی وقتی مثلاً عدد ۱۰ رو به تابع میدیم، انتظار داریم دهمین عدد فیبوناچی رو حساب کنه. پس فقط یه متغیر برای پارامتر این تابع لازم داریم.

ولی به خاطرِ بازگشتی بودن، اون آرگومان، خودش به عنوان آرگومان‌های درون تابع هم استفاده میشه. هر عدد فیبوناچی حاصل جمعِ دو عددِ فیبوناچیِ قبلی‌شه. پس علاوه بر متغیرِ ‏‎x‎‏، به ‏‎(x – 1)‎‏ و ‏‎(x – 2)‎‏ هم احتیاج داریم تا هر دو عدد قبل از آرگومان رو هم داشته باشیم.

fibonacci  :: Integral a => a -> a
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci x = (x – 1) (x – 2)
-- .نکته: هنوز کار نمی‌کنه

خوداتکایی

خیلی خوب، حالا رسیدیم به اصل مسئله. این تابع به چه نحوی باید به خودش ارجاع بده و خودش رو صدا بزنه؟ نگاه کنید ببینین تا اینجا به چه نتایجی رسیدیم: مرحله‌ی بعدی برای تولیدِ یه عدد فیبوناچی چیه؟ یک چیز اینکه ‏‎(x - 1)‎‏ و ‏‎(x - 2)‎‏ باید با هم جمع شن تا جواب بدن. اول با جمع ساده بین‌شون امتحان کنین، و تابع رو همونطور اجرا کنین:

fibonacci  :: Integral a => a -> a
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci x = (x - 1) + (x - 2)

اگه به این تابع عددِ ۶ رو بدین چی میشه؟

Prelude> fibonacci 6
 9

چرا؟ چون ((۲ – ۶) + (۱ – ۶)) مساویِ ۹. ولی اعداد فیبوناچی اینطور محاسبه نمیشن! عدد ششم در سری اعداد فیبوناچی ((۲ – ۶) + (۱ – ۶)) نیست. باید عضو پنجم اعداد فیبوناچی رو با عضو چهارم‌ش جمع کنیم، و عضو ششم رو بدست میاریم. این کار رو با ارجاعِ تابع به خودش انجام میدیم. در این مورد، باید مشخص کنیم که هم ‏‎(x - 1)‎‏ و هم ‏‎(x - 2)‎‏، هر دو خودشون اعداد فیبوناچی‌اند، پس تابع باید دو بار خودش رو صدا بزنه.

fibonacci  :: Integral a => a -> a
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci x =
  fibonacci (x - 1) + fibonacci (x - 2)

حالا اگه این تابع رو به مقدار ۶ اعمال کنیم، جوابِ دیگه‌ای می‌گیریم:

Prelude> fibonacci 6
8

چرا؟ چون اینطور بازگشتی محاسبه می‌کنه:

fibonacci 6 = fibonacci 5 + fibonacci 4

fibonacci 5 = fibonacci 4 + fibonacci 3

fibonacci 4 = fibonacci 3 + fibonacci 2

fibonacci 3 = fibonacci 2 + fibonacci 1

fibonacci 2 = fibonacci 1 + fibonacci 0

تابع رو با آرگومان‌های صفر و یک، برابرِ صفر و یک تعریف کردیم. پس در اون نقطه خوداتکایی می‌ایسته و شروع به جمعِ جواب‌ها می‌کنه:

fibonacci 0 =            0
fibonacci 1 =            1
fibonacci 2 =  (1 + 0 =) 1
fibonacci 3 =  (1 + 1 =) 2
fibonacci 4 =  (1 + 2 =) 3
fibonacci 5 =  (2 + 3 =) 5
fibonacci 6 =  (3 + 5 =) 8

اولش تصورِ نوشتن یه تابعِ بازگشتی، و اینکه چه مفهومی داره یه تابع خودش رو صدا بزنه ممکنه ترسناک باشه. ولی همونطور که می‌بینین، برای مواقعی که تابع به صورت تکراری به نتایج خودش رجوع می‌کنه کاربرد داره.