أهداف التعلم

في نهاية هذا القسم، ينبغي أن تكون قادرًا على

• تعريف دالّة عَودية لتوليد أعداد فيبوناتشي.

متتالية فيبوناتشي باستخدام العَودية

متتالية فيبوناتشي هي متتالية يكون فيها كل عدد مجموع العددين السابقين له في المتتالية. العددان الأولان هما 0 و 1. وهكذا، بدءًا من 0 و 1، العدد الثالث 0 + 1 = 1، والعدد التالي 1 + 1 = 2. متتالية الأعداد هي 0، 1، 1، 2، 3، 5، 8، 13، 21، 34، ... .

يمكن استخدام العَودية لحساب العدد النوني في متتالية فيبوناتشي. الحالات الأساسية هي 0 و 1. بعد ذلك، يُعطى العدد النوني بجمع العددين (ن - 1) و (ن - 2). وهكذا، fib(n) = fib(n - 1) + fib(n - 2)، وهو تعريف عَودي ينتهي بالحالات الأساسية f(0) = 0، و f(1) = 1.

بالنسبة للعَودية التي تستدعي دوال متعددة في الحالة العَودية، فإن تتبع مسار العَودية يكون مفيدًا. يُطلق على الهيكل المستخدم لتتبع الاستدعاءات التي تُجريها دالّة عَودية اسم شجرة العَودية. تتبع العرض التوضيحي أدناه شجرة العَودية لاستدعاء دالّة عَودية لحساب عدد فيبوناتشي لـ n = 5.

    """ Recursive Fibonacci function """

    def fib(n):
      # الحالة الأساسية
      if n == 0 or n == 1:
        return n
      # الحالة العَودية
      elif n > 1:
        return fib(n - 1) + fib(n - 2)
      # حالة الخطأ
      else:
        print("Fibonacci numbers begin at 0.")
        return

    # شِفرة اختبار
    print(fib(7))

    13

القاسم المشترك الأكبر (GCD)

القاسم المشترك الأكبر لعددين صحيحين موجبين عدد صحيح يقسمهما معًا. مثال: القاسم المشترك الأكبر للعددين 6 و 9 هو 3 لأن 3 × 2 = 6، و 3 × 3 = 9.

يُمكن إيجاد القاسم المشترك الأكبر بسهولة باستخدام طريقة إقليدس. تطرح طريقة إقليدس العدد الصحيح الأصغر من العدد الصحيح الأكبر بشكل عَودي حتى تُبلَغ حالة أساسية يكون فيها العددان الصحيحان متساويين. القاسم المشترك الأكبر قيمة العدد الصحيح عند بلوغ الحالة الأساسية.

    """ Find GCD using recursive implementation of Euclid's method """

    def gcd(a, b):
      if a == b: # الحالة الأساسية
        return a
      elif a < b: # الحالة العَودية
        return gcd(a, b - a)
      else:
        return gcd(a - b, a)

    # شِفرة اختبار
    print(gcd(24, 30))

    6