كيفية حساب قيمة فيبوناتشي لعدد ما بالدوال العودية recursion

الدالة العودية هي التي تقوم باستدعاء نفسها مرة أو أكثر لحساب حالات مختلفة حسب المشكلة

و فيبوناتشي، كل مرحلة هي مجموع مرحلتين السابقتين لها Fn = Fn-1 + Fn-2.

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

أي استدعائها العرمي بهذه الطريقة:

                          fib(5)   
                     /                \
               fib(4)                fib(3)   
             /        \              /       \ 
         fib(3)      fib(2)         fib(2)   fib(1)
        /    \       /    \        /      \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /     \
fib(1) fib(0)

ولها شرط توقف أي قيمتين ثابتتين F0 = 0 and F1 = 1.

#include<bits/stdc++.h>
using namespace std;
// الدالة العودية تعيد قيمة نوع رقم صحيح
// تستقبل الدالة تسلسل فيبوناتشي الذي نريد الحساب عنده
int fib(int n)
{
    if (n <= 1) // شرط توقف 0 - 1 - سالب
        return n; // نعيد نفس القيمة
  // نحسب الخطوتين السابقتين للخطوة الحالية
    return fib(n-1) + fib(n-2);
}
 
int main ()
{
    int n = 9;
  // cin >> n;  // إدخال من مستخدم
  
  // حساب
    cout << fib(n);
    return 0;
}

للاطلاع

• شرح التعاود من موسوعة حسوب