استدعاء ذاتي

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
شكل بصري للاستدعاء الذاتي يعرف بتأثير دروست. تحمل المرأة في الصورة جسم الذي يحتوي على صورة أصغر لها وهي حاملة نفس الجسم، والذي بدوره يحتوي على صورة أصغر لها وهي حاملة نفس الجسم، وهكذا.

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

تعريفات رسمية للاستدعاء الذاتي[عدل]

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

  • حالة أساس بسطية (أو عدة حالات)، و
  • مجموعة من القواعد التي تقلص كل الحالات الأخرى نحو حالة الأساس.

مثلا، التعريف بالاستدعاء الذاتي التالي هو تعريف لأسلاف شخص:

  • والدا شخص هم أسلافه (حالة الأساس)
  • والدا أسلاف شخص هم أيضا أسلافه (خطوة الاستدعاء الذاتي).

متتالية فيبوناتشي هي مثال تقليدي للاستدعاء الذاتي:

  • (Fib(0 هو 0 [حالة أساس]
  • (Fib(1 هو 1 [حالة أساس]
  • لكل الأعداد الصحيحة n > 1:
(Fib(n هو ((Fib(n-1) + Fib(n-2) [تعريف بالاستدعاء الذاتي]

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

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

كائنات معرفة بالاستدعاء الذاتي تشتمل على الدوال، المجموعات وخاصة الكسيريات.

فكاهات الاستدعاء الذاتي[عدل]

يتم استخدام الاستدعاء الذاتي بشكل فكاهي في علم الحاسوب، البرمجة، الفلسفة، أو كتب الرياضايات المدرسية; المثالان التاليان قد تكون تعريفات في القاموس: [1]

استدعاء ذاتي
راجع "استدعاء ذاتي".
استدعاء ذاتي
إذا لم تزل تعرفه، راجع "استدعاء ذاتي".

مثال آخر يوجد في فهرس في صفحة 269 في بعض نسخ كتاب كيرنيغان وريتشي "لغة البرمجة سي"; فإن الفهرس يشير باستدعاء ذاتي إلى نفسه

استعاء ذاتي 86, 139, 141, 182, 202, 269

فكاهة مشابهة تظهر في النسخة الإنجليزية من محرك بحث جوجل: عندما تبحث عن recursion، يقترح الموقع "Did you mean: Recursion."

اختصارات الاستدعاء الذاتي تمكن أن تكون نوع من الفكاهة في الاستدعاء الذاتي. بعض الأمثلة:

  • PHP هي اختصار لـ "PHP Hypertext Preprocessor"
  • WINE هي اختصار لـ "Wine Is Not an Emulator.
  • GNU هي اختصار لـ "GNU's Not Unix"

الاستدعاء الذاتي في الرياضيات[عدل]

مثلث سيربنسكي - استدعاء ذاتي لمثلثات لتشكيل مشبك هندسي.

المجموعات المعرفة بالاستدعاء الذاتي[عدل]

مثال: الأعداد الطبيعية[عدل]

المثال القانوني للمجموعات المعرفة بالاستدعاء الذاتي هو الأعداد الطبيعية:

1 في \mathbb{N}
إذا كان n في \mathbb{N}، إذن n + 1 في \mathbb{N}
مجموعة الأعداد الطبيعية هي المجموعة الأصغر التي تحقق الخاصتين السابقين.

دوال الاستدعاء الذاتي[عدل]

دالة قد تكون معرفة جزئياً بنفسها. مثال مألوف هو متتالية فيبوناتشي: (F(n) = F(n − 1) + F(n − 2. ليكون التعريف مفيداً، يجب أن يوصل إلى قيم غير معرفة بالاستدعاء الذاتي، في هذه الحالة F(0) == 0 و F(1) == 1.

دالة اكرمن هي دالة استدعاء ذاتي مشهورة، والتي بخلاف متتالية فيبوناتشي، لا يمكن التعبير عنها بدون الاستدعاء الذاتي.

الاستدعاء الذاتي في علم الحاسوب[عدل]

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

مثال تقليدي للاستدعاء الذاتي هو تعريف دالة العاملي، مثال بلغلة السي:

unsigned int factorial(unsigned int n) 
{
  if (n <= 1) 
    return 1;
  else
    return n * factorial(n-1);
}

تستدعي الدالة نفسها عودياً على نسخة أصغر من المدخل (n-1) وتضرب نتيجة الاستدعاء الذاتي بـ n، حتى تصل إلى حالة الأساس، بشكل مماثل للتعريف الرياضي للعاملي.

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

مبرهنة الاستدعاء الذاتي[عدل]

في نظرية المجموعات، هذه مبرهنة التي تضمن وجود دوال معرفة بالاستدعاء الذاتي. بإعطاء مجموعة X، عنصر a في X ودالة f: X \rightarrow X، تنص المبرهنة أنه هنالك دالة مميزة F: \mathbb{N} \rightarrow X (حيث أن \mathbb{N} ترمز مجموعة الأعداد الطبيعية شاملة الصفر) بحيث أن

F(0) = a
F(n + 1) = f(F(n))

لأي عدد طبيعي n.

برهان التميز[عدل]

لتكن F: \mathbb{N} \rightarrow X وG: \mathbb{N} \rightarrow X دالتين بحيث أن:

F(0) = a
G(0) = a
F(n + 1) = f(F(n))
G(n + 1) = f(G(n))

بحث أن a هو عنصر في X.

بالإمكان البرهنة بالاستقراء أن F(n) = G(n) لكل الأعداد الطبيعية n:

الأساس: F(0) = a = G(0) وبالتالي فإن المساواة تنطبق أيضا على n = 0.
خطوة الاستقراء: لنفرض أن F(k) = G(k) لبعض k \in \mathbb{N}. إذن F(k+1) = f(F(k)) = f(G(k)) = G(k+1).
ومن هنا F(k) = G(k) يؤدي إلى F(k+1) = G(k+1).

بالاسقراء , F(n) = G(n) لكل n \in \mathbb{N}.

أمثلة[عدل]

بعض العلاقات العودية الشائعة:

وصلات خارجية[عدل]

مراجع[عدل]

  1. ^ Hunter، David (2011). Essentials of Discrete Mathematics. Jones and Bartlett. صفحة 494. 
  • Johnsonbaugh, Richard (2004). Discrete Mathematics. Prentice Hall. ISBN 0-13-117686-2. 
  • Hofstadter, Douglas (1999). Gödel, Escher, Bach: an Eternal Golden Braid. Basic Books. ISBN 0-465-02656-7. 
  • Shoenfield, Joseph R. (2000). Recursion Theory. A K Peters Ltd. ISBN 1-56881-149-7. 
  • Causey, Robert L. (2001). Logic, Sets, and Recursion. Jones & Bartlett. ISBN 0-7637-1695-2. 
  • Cori, Rene; Lascar, Daniel; Pelletier, Donald H. (2001). Recursion Theory, Godel's Theorems, Set Theory, Model Theory. Oxford University Press. ISBN 0-19-850050-5. 
  • Barwise, Jon; Moss, Lawrence S. (1996). Vicious Circles. Stanford Univ Center for the Study of Language and Information. ISBN 0-19-850050-5.  - offers a treatment of corecursion.
  • Rosen, Kenneth H. (2002). Discrete Mathematics and Its Applications. McGraw-Hill College. ISBN 0-07-293033-0. 
  • Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). Introduction to Algorithms. Mit Pr. ISBN 0-262-03293-7. 
  • Kernighan, B.; Ritchie, D. (1988). The C programming Language. Prentice Hall. ISBN 0-13-110362-8. 
  • Stokey, Nancy,; Robert Lucas; Edward Prescott (1989). Recursive Methods in Economic Dynamics. Harvard University Press. ISBN 0674750969. 
  • Hungerford (1980). Algebra. Springer. ISBN 978-0387905181. , first chapter on set theory.