استدعاء ذاتي

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

استدعاء ذاتي بالإنگليزية: Recursion يعني تكرار الشيء، ويستخدم هذا المصطلح في الرياضيات وفي علوم الحاسوب ليعني تكرار التعريف للدالة نفسها. ويستخدم لتكرار الدالة مرة ثانية وإذا تمت عملية الاستدعاء الذاتي لمرة ثالثة يكرر نفس الشي. وعملية الاستدعاء الذاتي هي إستدعاء الشيء لنفسه. وفي البرمجة عندما تتم عملية الاستدعاء الذاتي للدالة أبجد فيتم كتابتها مرة ثانية وهكذا.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

التعريفات الشكلية للاستدعاء الذاتي

Recursion in a screen recording program, where the smaller window contains a snapshot of the entire screen.

ونفس الأمر بالنسبة للبرمجة ففرضا لدينا الدالة Function التالية GetChile(ID)

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


الاستدعاء الذاتي في اللغة

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

استدعاء ذاتي لمثلثات محصورة في مثلث سيرپنسكي لتشكل عقد هندسي.

فئات معرَّفة بالاستدعاء الذاتي

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

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

1 is in
فلو n هي في ، فإذن n + 1 is in
The set of natural numbers is the smallest set satisfying the previous two properties.

مثال: فئة التقارير التي يمكن الوصول إليها بحق

Another interesting example is the set of all "true reachable" propositions in an axiomatic system.

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

This screenshot of a web page includes the screen shot itself.


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

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

برهان التفرد

Take two functions and بحيث:

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

ويمكن الاثبات باستخدام الاستقراء الرياضي أن لكل الأعداد الطبيعية n:

الحالة الأساسية: لذلك فالتساوي ساري لحالة .
Inductive Step: افترض لبعض . Then
Hence F(k) = G(k) implies F(k+1) = G(k+1).

By Induction, for all .

أمثلة

بعض علاقات الاستدعاء الذاتي الشائعة هي:

انظر أيضاً

الهامش


وصلات خارجية

  • 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.CS1 maint: multiple names: authors list (link)
  • Barwise, Jon; Moss, Lawrence S. (1996). Vicious Circles. Stanford Univ Center for the Study of Language and Information. ISBN 0-19-850050-5.CS1 maint: multiple names: authors list (link) - 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.CS1 maint: multiple names: authors list (link)
  • Kernighan, B.; Ritchie, D. (1988). The C programming Language. Prentice Hall. ISBN 0-13-110362-8.CS1 maint: multiple names: authors list (link)
  • Stokey, Nancy,; Robert Lucas; Edward Prescott (1989). Recursive Methods in Economic Dynamics. Harvard University Press. ISBN 0674750969.CS1 maint: multiple names: authors list (link)
  • Hungerford; title=Algebra (1980). Springer. ISBN 978-0387905181. Missing pipe in: |author= (help); Missing or empty |title= (help)CS1 maint: multiple names: authors list (link), first chapter on set theory.
  • Recursion - tutorial by Alan Gauld
  • A Primer on Recursion- contains pointers to recursion in Formal Languages, Linguistics, Math and Computer Science
  • Zip Files All The Way Down
  • Nevins, Andrew and David Pesetsky and Cilene Rodrigues. Evidence and Argumentation: A Reply to Everett (2009). Language 85.3: 671--681 (2009)
  • Kaan, E. – Swaab, T. Y. (2002) “The brain circuitry of syntactic comprehension”, Trends in Cognitive Sciences, vol. 6, Issue 8, 350-356.