جلسه ۶۰: محاسبه دنباله فیبوناچی به روش بازگشتی در جاوا

در این درس ، ما یاد خواهیم گرفت که چگونه دنباله فیبوناچی را با روش بازگشتی محاسبه کنیم.موارد زیر را بیان خواهیم کرد:

• دنباله فیبوناچی چیست؟
• فرمول ریاضی
• پیاده سازی کد
• تفسیر کد
• متد main
• متد بازگشتی
• حالت پایه
• حالت بازگشتی
• نمایش روش بازگشتی در پشته

دنباله فیبوناچی چیست؟

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

۰, ۱, ۱, ۲, ۳, ۵, ۸, ۱۳, ۲۱, ۳۴, ۵۵, ۸۹, ۱۴۴, …

فرمول ریاضی

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

$F$_n $=F$_n-2$+F$_n-1

به طور پیش فرض ، جمله اول و دوم در دنباله به ترتیب ۰ و ۱ است.

$F$₁ $=\mathrm{۰}$

$F$₂ $=\mathrm{۱}$

$F$₃ $=F$₁$+F$₂ $=\mathrm{۱}+\mathrm{۰}=\mathrm{۱}$

$F$₄ $=F$₂$+F$₃ $=\mathrm{۱}+\mathrm{۱}=\mathrm{۲}$

$F$₅ $=F$₃$+F$₄ $=\mathrm{۱}+\mathrm{۲}=\mathrm{۳}$

$F$₆ $=F$₄$+F$₅ $=\mathrm{۲}+\mathrm{۳}=\mathrm{۵}$

$F$₇ $=F$₅$+F$₆ $=\mathrm{۳}+\mathrm{۵}=\mathrm{۸}$

$F$₈ $=F$₆$+F$₇ $=\mathrm{۵}+\mathrm{۸}=\mathrm{۱}\mathrm{۳}$

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

پیاده سازی کد

با تغییر متغیر input در کد زیر می توانید تعدادی دلخواه از جملات فیبوناچی را چاپ کنید.

class FibonacciClass {

    private static int fibonacci(int n) {
        // Base case 
        if (n <= 1) {
            return n;
        }
        // Recursive case
        else {
            return (fibonacci(n-1) + fibonacci(n-2));
        }
    }

    public static void main( String args[] ) {
        int input = 5;
        System.out.println("Fibonacci sequence for the first " + input + " elements is:");

        // Loop to print all the fibonacci sequence elements
        int i = 0;
        while (i < input) {
            System.out.print(fibonacci(i) + " ");
            i++;
        }
    }
}

تفسیر کد

در کد بالا ، متد fibonacci یک متد بازگشتی است ، زیرا خود را در بدنه اش فراخوانی می کند. در زیر توضیحات کد بالا آورده شده است:

متد main

• در داخل متد main ، ما دو متغیر integer با نام های i و input تعریف کرده ایم.
• i به عنوان شمارنده حلقه استفاده شده است و input تعداد جملاتی از دنباله فیبوناچی است که تولید می شود.
• حلقه while به تعداد دفعات input اجرا می شود و به تعداد input ، اعداد توالی فیبوناچی را در ورودی چاپ می کند. به عنوان مثال ، وقتی input برابر ۵ باشد ، متد main پنج عدد اول دنباله فیبوناچی را چاپ می کند.

متد بازگشتی

• نوع بازگشتی این متد int است زیرا تمام مقادیر دنباله فیبوناچی عدد صحیح هستند.
• این متد یک عدد صحیح ، n را به عنوان آرگومان ورودی دریافت می کند.

حالت پایه

• حالت پایه متد در خط ۵ تعریف شده است که در صورتی که در این خط شرط if یعنی n <= 1 برقرار باشد، متد بازگشتی خاتمه می یابد و مقدار جمله n ام از دنباله فیبوناچی را باز می گرداند.

حالت بازگشتی

• اگر شرط حالت پایه برقرار نباشد ، این متد وارد بلوک else می شود (از خط ۹ تا خط ۱۱) ، جایی که با آرگمان های ورودی فرمول ریاضی ، خودش را به صورت بازگشتی فراخوانی می کند: "retracement (n-1) + retracement (n-2) همانطور که در خط ۱۰ مشاهده می شود. آرگومان های ورودی با فرمول ریاضی یافتن یک جمله در دنباله فیبوناچی مطابقت دارند.

$F$_n $=F$_n-2$+F$_n-1

نمایش روش بازگشتی در پشته

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