مرجع
آخر الزيارات

عودية (علم الحاسوب)

723 كلمة•0 مشاهدة•🗒️ منذ 13 يوماً
باختصار: العودية أو الاستدعاء الذاتي في علم الحاسوب هو طريقة التي فيها الحل لمسألة ما يعتمد على حلول مسائل أصغر من نفس النوع. تتناول المقالة 26 قسماً، منها «private static int fib(int k) {»، «} else {» و«{».
المحتويات
  1. private static int fib(int k) {
  2. } else {
  3. {
  4. }
  5. بحث ثنائي
  6. /**
  7. *
  8. }
  9. /*
  10. return binary_search(data, toFind, start, mid-1);
  11. return n
  12. */
  13. }
  14. برج هانوي
  15. */
  16. /*
  17. }
  18. return -1;
  19. العاملي
  20. فيبوناتشي
  21. return mid;
  22. {
  23. قاسم مشترك أكبر
  24. end is the maximum array index
  25. toFind is the integer to search for,
  26. my ($n) = @_;
عودية (علم الحاسوب)

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

إضافةً إلى ذلك، تدعم أغلب لغات البرمجة الاستدعاء الذاتي عن طريق السماح لدالة أن تستدعي نفسها ضمن نص البرنامج نفسه. بعض لغات البرمجة الوظيفة لا تعرّف مبان تكرارية (looping constructs) ولكن تعتمد فقط على الاستدعاء الذاتي لتكرار تنفيذ كود معين. برهنت نظرية الحاسوبية أن اللغات التي تستعمل الاستدعاء الذاتي فقط معادلة رياضياً للغات الحتمية، بمعنى أنه باستطاعتهم حل أي نوع من المسائل دون الحاجة لمباني التحكم النموذجية مثل حلقات "while" أو "for".

برامج الاستدعاء الذاتي

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

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

private static int fib(int k) {

  • // Base Cases:
  • // If k == 0 then fib(k) = 0.
  • // If k == 1 then fib(k) = 1.
  • if (k < 2) {
  • return k;

} else {

return fib(n - 1) + fib(n - 2);

}

{

  • //Get the midpoint.
  • int mid = start + (end - start)/2; //Integer division
  • //Stop condition.
  • if (start > end)

}

  • علاقة تكرارية للفيبوناتشي:
  • bn = bn-1 + bn-2
  • b1 == 1, b0 == 0

بحث ثنائي

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

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

مثال لتطبيق البحث الثنائي باستخدام لغة سي:

/**

* Recursively calculate the kth Fibonacci number.

*

  • * @param k indicates which (positive) Fibonacci number to compute.
  • * @return the kth Fibonacci number.
  • */

}

  • باستخدام ليسب:
  • (defun fib (n)
  • (cond ((= n 0) 0)
  • ((= n 1) 1)
  • (t (+ (fib (- n 1))
  • (fib (- n 2))))))
  • باستخدام بيرل:
  • sub fib {

/*

  • Call binary_search with proper initial conditions.
  • INPUT:
  • data is an array of integers SORTED in ASCENDING order,

return binary_search(data, toFind, start, mid-1);

  • else //Data is less than toFind, search upper half
  • return binary_search(data, toFind, mid+1, end);
  • }
  • انظر كذلك
  • استدعاء ذاتي
  • برمجة وظيفية
  • خوارزمية فرق تسد

return n

  • else:
  • return fib(n-1) + fib(n-2)
  • باستخدام جافاسكربت:
  • function fib (n) {
  • if (!n) {
  • return 0;
  • } else if (n <= 2) {
  • return 1;

*/

علاوةً على ذلك، int binary_search(int *data, int toFind, int start, int end)

}

  • تطبيق باستخدام بايثون:
  • def fib(n):
  • if n < 2:

برج هانوي

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

علاقة تكرارية لبرج هانوي:

*/

int search(int *data, int toFind, int count)

/*

  • Binary Search Algorithm.
  • INPUT:
  • data is a array of integers SORTED in ASCENDING order,
  • toFind is the integer to search for,
  • start is the minimum array index,

}

  • // Recursive Case:
  • // If k >= 2 then fib(k) = fib(k-1) + fib(k-2).
  • else {
  • return fib(k-1) + fib(k-2);
  • }

return -1;

else if (data[mid] == toFind) //Found?

العاملي

بالإمكان كتابة الدالة كعلاقة تكرارية:

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

فيبوناتشي

تطبيق باستخدام جافا:

دالة رياضية معروفة أخرى هي دالة التي تحسب أعداد فيبوناتشي:

return mid;

وعلى صعيد آخر، else if (data[mid] > toFind) //Data is greater than toFind, search lower half

{

  • // Start = 0 (beginning index)
  • // End = count - 1 (top index)
  • return binary_search(data, toFind, 0, count-1);
  • }

قاسم مشترك أكبر

ومن جهة أخرى، علاقة تكرارية للقاسم المشترك الأكبر، بحيث أن يمثل الباقي من قسمة :

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

end is the maximum array index

  • OUTPUT:
  • position of the integer toFind within array data,
  • -1 if not found

toFind is the integer to search for,

  • count is the total number of elements in the array
  • OUTPUT:
  • result of binary_search

my ($n) = @_;

($n < 2) ? $n : fib($n - 2) + fib($n - 1);

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.