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

Question

أحاول حقًا أن ألتف عقلي حول كيفية عمل العودية وفهم الخوارزميات العودية.على سبيل المثال، الكود أدناه يُرجع 120 عندما أدخل 5، أعذر جهلي، وأنا لا أفهم السبب؟

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n-1)

answer = int (raw_input('Enter some number: '))

print fact(answer)

Answer 1

يتيح المشي من خلال التنفيذ.

giveacodicetagpre.

الآن يتيح جمع النتيجة.

giveacodicetagpre.

بديلا في نتيجةنا لحقيقة (4)

giveacodicetagpre.

بديلا في نتيجةنا لحقيقة (3)

giveacodicetagpre.

بديلا في نتيجةنا لحقيقة (2)

giveacodicetagpre.

بديلا في نتيجةنا لحقيقة (1)

giveacodicetagpre.

بديلا في نتيجةنا لحقيقة (0)

giveacodicetagpre.

وهناك لديك.العودية هي عملية كسر مشكلة أكبر من خلال النظر إليها كصغرت بنجاح حتى تصل إلى حالة تافهة (أو "قاعدة").

Answer 2

قم بتقسيم المشكلة إلى خطوات تنفيذها.

fact(5)
| 5  * fact(4)
|| 5 * (4 * fact(3))
||| 5 * (4 * (3 * fact(2))
|||| 5 * (4 * (3 * (2 * fact(1))))
||||| 5 * (4 * (3 * (2 * (1 * fact(0)))))
|||||| 5 * 4 * 3 * 2 * 1 * 1
120

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

Answer 3

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

fact(1) has n of 5
   fact(2) has n of 4
      fact(3) has n of 3
         fact(4) has n of 2
            fact(5) has n on 1
               fact(6) has n of 0

الأعمق (هنا، fact(6) الأعمق) يتم حسابها بالكامل قبل أن تتمكن المستويات الموجودة فوقها في مكدس الاستدعاءات من الانتهاء.

لذا

• fact(6) ترجع 1 إلى fact(5) (حالة إنهاء الخدمة).
• fact(5) ترجع 1 إلى fact(4) (1*1)
• fact(4) إرجاع 2 إلى fact(3) (2*1)
• fact(3) ترجع 6 إلى fact(2) (3*2)
• fact(2) إرجاع 24 إلى fact(1) (4*6)
• وأخيرا fact(1) ترجع 120 (5*24) إلى المتصل بها، مهما كان ذلك.

Answer 4

وظيفة متكررة هي واحدة تستدعي نفسها وتستمر في القيام بذلك حتى يتم الانتهاء من التقييم ويتم إنتاج نتيجة.المفتاح مع الوظيفة العذوطة لديك أعلاه هو العودة X * حقيقة (X-1)

لذلك إذا قمت بإدخال 5، فسوف تنفذ 5 * حقيقة (5-1) * حقيقة 4-1) .... وهلم جرا حتى يضرب 0 ثم يعود 1. لذلك سيكون لديك 5 * 4 * 3* 2 * 1 وهو 120.

يستمر في تخصيص المتغيرات على المكدس.لذلك إذا وضعت رقما مرتفعا للغاية، فقد يؤدي ذلك إلى استثناء تجاوز سعة مكدس.ما لم تستخدم شيء يسمى تحسين دعوة الذيل (TCO) الذي يحول الدالة العودية إلى حلقة وينظف الذاكرة المخصصة.