التفكير التكراري في بايثون

جدول المحتويات

• عزيزي سانتا كلوز البيثوني …
  
• الوظائف العودية في بايثون
  
• الحفاظ على الدولة
  
• هياكل البيانات العودية في بايثون
  
• التكرار الساذج هو ساذج
  
• تفاصيل مزعجة
  
• زعنفة
  
• المراجع
  

“من بين جميع الأفكار التي قدمتها للأطفال ، تبرز العودية باعتبارها الفكرة الوحيدة القادرة بشكل خاص على إثارة استجابة حماسية.”

– سيمور بابيرت ، Mindstorms

غالبًا ما تبدو المشكلات (في الحياة وأيضًا في علوم الكمبيوتر) كبيرة ومخيفة. ولكن إذا واصلنا تقطيعها بعيدًا ، فغالبًا ما يمكننا تقسيمها إلى أجزاء أصغر تافهة بما يكفي لحلها. هذا هو جوهر التفكير التكراري ، وهدفي في هذه المقالة هو تزويدك ، عزيزي القارئ ، بالأدوات المفاهيمية اللازمة للتعامل مع المشكلات من وجهة النظر العودية هذه.

معًا ، سنتعلم كيفية التعامل مع العودية في برامج بايثون من خلال إتقان مفاهيم مثل الوظائف العودية وهياكل البيانات العودية. سنتحدث أيضًا عن الحفاظ على الحالة أثناء العودية وتجنب إعادة الحساب عن طريق تخزين النتائج مؤقتًا. هذا سيكون ممتعا جدا. إلى الأمام وإلى الأعلى!

عزيزي سانتا كلوز البيثوني …

أدرك أنه بصفتنا رفقاء في Pythonistas ، نحن جميعًا بالغون موافقون هنا ، لكن يبدو أن الأطفال يستحوذون على جمال التكرار بشكل أفضل. لذا دعونا لا نكون بالغين هنا للحظة ونتحدث عن كيفية استخدام العودية لمساعدة سانتا كلوز.

هل تساءلت يومًا كيف يتم تسليم هدايا عيد الميلاد؟ أنا متأكد من ذلك ، وأعتقد أن لدى سانتا كلوز قائمة بالمنازل التي يمر بها. يذهب إلى منزل ، ويسقط الهدايا ، ويأكل البسكويت والحليب ، وينتقل إلى المنزل التالي في القائمة. نظرًا لأن هذه الخوارزمية لتقديم العروض تستند إلى بناء حلقة واضحة ، فإنها تسمى خوارزمية تكرارية.

خوارزمية التسليم الحالي التكراري المطبقة في Python:

houses = ["Eric's house", "Kenny's house", "Kyle's house", "Stan's house"]

def deliver_presents_iteratively():
    for house in houses:
        print("Delivering presents to", house)

>>> deliver_presents_iteratively()
Delivering presents to Eric's house
Delivering presents to Kenny's house
Delivering presents to Kyle's house
Delivering presents to Stan's house

لكني أشعر بسانتا. في مثل عمره ، لا ينبغي أن يضطر إلى تسليم جميع الهدايا بنفسه. أقترح خوارزمية يمكنه من خلالها تقسيم عمل تقديم الهدايا بين أقزامه:

1. تعيين قزم وإعطاء كل العمل له
2. قم بتعيين الألقاب والمسؤوليات إلى الجان بناءً على عدد المنازل المسؤولة عنها:
   > 1 هو مدير ويمكنه تعيين اثنين من الجان وتقسيم عمله بينهما
   = 1 هو عامل وعليه تسليم الهدايا إلى المنزل المخصص له

هذا هو الهيكل النموذجي للخوارزمية العودية. إذا كانت المشكلة الحالية تمثل حالة بسيطة ، قم بحلها. إذا لم يكن الأمر كذلك ، فقم بتقسيمها إلى مشكلات فرعية وطبق نفس الإستراتيجية عليها.

الخوارزمية الخاصة بالتسليم الحالي التكراري المطبقة في Python:

houses = ["Eric's house", "Kenny's house", "Kyle's house", "Stan's house"]

# Each function call represents an elf doing his work 
def deliver_presents_recursively(houses):
    # Worker elf doing his work
    if len(houses) == 1:
        house = houses[0]
        print("Delivering presents to", house)

    # Manager elf doing his work
    else:
        mid = len(houses) // 2
        first_half = houses[:mid]
        second_half = houses[mid:]

        # Divides his work among two elves
        deliver_presents_recursively(first_half)
        deliver_presents_recursively(second_half)

>>> deliver_presents_recursively(houses)
Delivering presents to Eric's house
Delivering presents to Kenny's house
Delivering presents to Kyle's house
Delivering presents to Stan's house

الوظائف العودية في بايثون

الآن بعد أن أصبح لدينا حدس حول العودية ، دعنا نقدم التعريف الرسمي للدالة العودية. الوظيفة العودية هي وظيفة محددة من حيث نفسها عبر تعبيرات مرجعية ذاتية.

هذا يعني أن الوظيفة ستستمر في استدعاء نفسها وتكرار سلوكها حتى يتم استيفاء شرط لإرجاع نتيجة. تشترك جميع الوظائف العودية في بنية مشتركة تتكون من جزأين: الحالة الأساسية والحالة العودية.

لتوضيح هذه البنية ، دعنا نكتب دالة عودية لحساب n !:

1. قسّم المشكلة الأصلية إلى حالات أبسط لنفس المشكلة. هذه هي الحالة العودية:
   

   n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2 x 1
   n! = n x (n−1)!

2. نظرًا لتقسيم المشكلة الكبيرة إلى مشاكل أقل تعقيدًا على التوالي ، يجب أن تصبح هذه المشكلات الفرعية في النهاية بسيطة جدًا بحيث يمكن حلها دون مزيد من التقسيمات الفرعية. هذه هي الحالة الأساسية:
   

   n! = n x (n−1)! 
   n! = n x (n−1) x (n−2)!
   n! = n x (n−1) x (n−2) x (n−3)!
   ⋅
   ⋅
   n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3!
   n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2!
   n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2 x 1!

هنا ، 1! هي الحالة الأساسية لدينا ، وهي تساوي 1.

دالة تكرارية لحساب ن! تم تنفيذه في Python:

def factorial_recursive(n):
    # Base case: 1! = 1
    if n == 1:
        return 1

    # Recursive case: n! = n * (n-1)!
    else:
        return n * factorial_recursive(n-1)

>>> factorial_recursive(5)
120

خلف الكواليس ، تضيف كل مكالمة متكررة إطار مكدس (يحتوي على سياق التنفيذ الخاص به) إلى مكدس الاستدعاءات حتى نصل إلى الحالة الأساسية. بعد ذلك ، يبدأ المكدس في التراجع حيث تُرجع كل مكالمة نتائجها:

الحفاظ على الدولة

عند التعامل مع الدوال العودية ، ضع في اعتبارك أن كل استدعاء متكرر له سياق تنفيذ خاص به ، لذلك للحفاظ على الحالة أثناء العودية ، عليك إما:

• قم بربط الحالة من خلال كل استدعاء تعاودي بحيث تكون الحالة الحالية جزءًا من سياق تنفيذ المكالمة الحالية
• حافظ على الدولة في النطاق العالمي

يجب أن تجعل المظاهرة الأمور أكثر وضوحًا. لنحسب 1 + 2 + 3 ⋅⋅⋅⋅ + 10 باستخدام العودية. الحالة التي يجب أن نحافظ عليها هي (الرقم الحالي الذي نضيفه ، المجموع التراكمي حتى الآن).

وإليك كيفية القيام بذلك عن طريق ربطه خلال كل مكالمة متكررة (أي تمرير الحالة الحالية المحدثة إلى كل استدعاء متكرر كوسيطات):

def sum_recursive(current_number, accumulated_sum):
    # Base case
    # Return the final state
    if current_number == 11:
        return accumulated_sum

    # Recursive case
    # Thread the state through the recursive call
    else:
        return sum_recursive(current_number + 1, accumulated_sum + current_number)

# Pass the initial state
>>> sum_recursive(1, 0)
55

إليك كيفية الحفاظ على الدولة من خلال إبقائها في النطاق العالمي:

# Global mutable state
current_number = 1
accumulated_sum = 0


def sum_recursive():
    global current_number
    global accumulated_sum
    # Base case
    if current_number == 11:
        return accumulated_sum
    # Recursive case
    else:
        accumulated_sum = accumulated_sum + current_number
        current_number = current_number + 1
        return sum_recursive()

>>> sum_recursive()
55

أفضل ربط الحالة من خلال كل مكالمة متكررة لأنني أجد أن الحالة المتغيرة العالمية شريرة ، لكن هذه مناقشة لوقت لاحق.

هياكل البيانات العودية في بايثون

تكون بنية البيانات متكررة إذا كان من الممكن تعريفها من حيث نسخة أصغر من نفسها. القائمة هي مثال على بنية البيانات العودية. اسمحوا لي أن أوضح. افترض أن لديك قائمة فارغة فقط تحت تصرفك ، والعملية الوحيدة التي يمكنك إجراؤها عليها هي:

# Return a new list that is the result of
# adding element to the head (i.e. front) of input_list
def attach_head(element, input_list):
    return [element] + input_list

باستخدام القائمة الفارغة وعملية attach_head ، يمكنك إنشاء أي قائمة. على سبيل المثال ، دعونا ننشئ [1، 46، -31، “مرحبًا”]:

attach_head(1,                                                  # Will return [1, 46, -31, "hello"]
            attach_head(46,                                     # Will return [46, -31, "hello"]
                        attach_head(-31,                        # Will return [-31, "hello"]
                                    attach_head("hello", [])))) # Will return ["hello"]

[1, 46, -31, 'hello']

1. بدءًا بقائمة فارغة ، يمكنك إنشاء أي قائمة عن طريق تطبيق وظيفة attach_head بشكل متكرر ، وبالتالي يمكن تعريف بنية بيانات القائمة بشكل متكرر على النحو التالي:
   

          +---- attach_head(element, smaller list)
   list = +
          +---- empty list

2. يمكن أيضًا اعتبار التكرار على أنه تكوين وظيفة مرجعية ذاتية. نطبق دالة على وسيطة ، ثم نمرر هذه النتيجة كوسيطة لتطبيق آخر لنفس الوظيفة ، وهكذا. تكرار إنشاء attach_head مع نفسها هو نفس استدعاء attach_head لنفسها بشكل متكرر.
   

القائمة ليست هي بنية البيانات العودية الوحيدة. تشمل الأمثلة الأخرى المجموعة والشجرة والقاموس وما إلى ذلك.

تتوافق هياكل البيانات التكرارية والوظائف التكرارية معًا مثل الخبز والزبدة. غالبًا ما يمكن تصميم بنية الوظيفة العودية بعد تعريف بنية البيانات العودية التي تتخذها كمدخلات. اسمحوا لي أن أوضح ذلك من خلال حساب مجموع كل عناصر القائمة بشكل متكرر:

def list_sum_recursive(input_list):
    # Base case
    if input_list == []:
        return 0

    # Recursive case
    # Decompose the original problem into simpler instances of the same problem
    # by making use of the fact that the input is a recursive data structure
    # and can be defined in terms of a smaller version of itself
    else:
        head = input_list[0]
        smaller_list = input_list[1:]
        return head + list_sum_recursive(smaller_list)

>>> list_sum_recursive([1, 2, 3])
6

التكرار الساذج هو ساذج

تم تحديد أرقام فيبوناتشي في الأصل من قبل عالم الرياضيات الإيطالي فيبوناتشي في القرن الثالث عشر لنمذجة نمو مجموعات الأرانب. توقع فيبوناتشي أن عدد أزواج الأرانب المولودين في سنة معينة يساوي عدد أزواج الأرانب التي ولدت في كل عام من العامين السابقين ، بدءًا من زوج واحد من الأرانب في السنة الأولى.

لحساب عدد الأرانب التي ولدت في السنة التاسعة ، حدد علاقة التكرار:

Fn = Fn-1 + Fn-2

الحالات الأساسية هي:

F0 = 0 and F1 = 1

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

def fibonacci_recursive(n):
    print("Calculating F", "(", n, ")", sep="", end=", ")

    # Base case
    if n == 0:
        return 0
    elif n == 1:
        return 1

    # Recursive case
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

>>> fibonacci_recursive(5)
Calculating F(5), Calculating F(4), Calculating F(3), Calculating F(2), Calculating F(1), 
Calculating F(0), Calculating F(1), Calculating F(2), Calculating F(1), Calculating F(0), 
Calculating F(3), Calculating F(2), Calculating F(1), Calculating F(0), Calculating F(1),

5

كان اتباع التعريف العودي لعدد فيبوناتشي التاسع غير فعال إلى حد ما. كما ترى من المخرجات أعلاه ، نحن نعيد حساب القيم دون داع. دعونا نحاول تحسين fibonacci_recursive عن طريق التخزين المؤقت لنتائج كل حساب Fibonacci Fk:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_recursive(n):
    print("Calculating F", "(", n, ")", sep="", end=", ")

    # Base case
    if n == 0:
        return 0
    elif n == 1:
        return 1

    # Recursive case
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

>>> fibonacci_recursive(5)
Calculating F(5), Calculating F(4), Calculating F(3), Calculating F(2), Calculating F(1), Calculating F(0),

5

lru_cache هو مصمم يقوم بتخزين النتائج مؤقتًا. وبالتالي ، نتجنب إعادة الحساب عن طريق التحقق صراحة من القيمة قبل محاولة حسابها. شيء واحد يجب مراعاته حول lru_cache هو أنه نظرًا لأنه يستخدم قاموسًا لتخزين النتائج مؤقتًا ، يجب أن تكون الوسيطات الموضعية والكلمات الرئيسية (التي تعمل كمفاتيح في هذا القاموس) للوظيفة قابلة للتجزئة.

تفاصيل مزعجة

بايثون ليس لديها دعم لإلغاء استدعاء الذيل. نتيجة لذلك ، يمكن أن تتسبب في تجاوز مكدس إذا انتهى بك الأمر باستخدام إطارات مكدس أكثر من عمق مكدس الاستدعاءات الافتراضي:

>>> import sys
>>> sys.getrecursionlimit()
3000

ضع هذا القيد في الاعتبار إذا كان لديك برنامج يتطلب تكرارًا عميقًا.

أيضًا ، لا تدعم هياكل البيانات القابلة للتغيير في Python المشاركة الهيكلية ، لذا فإن معاملتها مثل هياكل البيانات غير القابلة للتغيير ستؤثر سلبًا على مساحتك وكفاءة GC (جمع البيانات المهملة) لأنك ستنتهي بدون داعٍ إلى نسخ الكثير من الكائنات القابلة للتغيير. على سبيل المثال ، لقد استخدمت هذا النمط لتحليل القوائم والتكرار عليها:

>>> input_list = [1, 2, 3]
>>> head = input_list[0]
>>> tail = input_list[1:]
>>> print("head --", head)
head -- 1
>>> print("tail --", tail)
tail -- [2, 3]

فعلت ذلك لتبسيط الأمور من أجل الوضوح. ضع في اعتبارك أن الذيل يتم إنشاؤه عن طريق النسخ. يمكن أن يؤثر القيام بذلك بشكل متكرر على قوائم كبيرة سلبًا على مساحتك وكفاءة GC.

زعنفة

طُلب مني ذات مرة شرح العودية في مقابلة. أخذت ورقة وكتبت من فضلك اقلبها على كلا الجانبين. لم يستوعب القائم بإجراء المقابلة الدعابة ، ولكن الآن بعد أن قرأت هذا المقال ، أتمنى أن تفعل 🙂 Happy Pythoning!

المراجع

1. التفكير التكراري
   
2. المخادع الصغير
   
3. مفاهيم وتقنيات ونماذج برمجة الحاسوب
   
4. دليل تصميم الخوارزمية
   
5. برمجة هاسكل من المبادئ الأولى