من كتاب كيف تفكر كعالم كمبيوتر لغه جافا الفصل السادس العمليات المثمرة : المزيد من التعاود

[عماد الكامل]

المزيد من التعاود

الآن بعد أن أصبح لدينا عمليات ترجِـع قيماً، أصبح لدينا لغة برمجة كاملة وفقاً لمعيار تورين
(Turing complete programming language)، وذلك يعني أننا قادرين الآن أن نحسب أي شيء قابل للحوسبة، وذلك بالنسبة للتعاريف المنطقية لكلمة "حوسبة".
تم تطوير هذه الفكرة على يد العالمان ألونزو تشيرتش (Alonzo Church) وآلان تورين (Alan Turing)، وهي تعرف بفرضية تشيرتش-تورين. يمكنك قراءة المزيد عنها على [IMG]http://en.wikipedia.org/wiki/Turing_thesis[/url].
لأعطيك فكرة عما يمكنك فعله باستخدام الأدوات التي تعلمناها حتى الآن، دعنا نلق نظرة على بعض العمليات المستخدمة في حساب توابع رياضية معرفة تعاودياً. التعريف التعاودي مشابه لتعريف دائري، بمعنى أن التعريف يحتوي على مرجع يربطه بالشيء المعرَّف. التعريف الدائري الحقيقي ليس مفيداً جداً بشكل عام:
التعاودية: صفة تستخدم لوصف العمليات التعاودية.
إذا قرأت التعريف السابق في قاموس، فقد تنزعج حقاً. من جهة أخرى، إذا بحثت عن تعريف الرياضي للتابع العاملي (factorial)، فقد تصل إلى شيء مثل:

0! = 1
n! = n . (n − 1)!

(غالباً ما يتم ترميز التابع العاملي بالرمز !، الذي لا يجب الخلط بينه وبين عامل Java المنطقي ! الذي يعني النفي (NOT)). هذا التعريف يقول أن 0 عاملي يساوي 1، وأن عاملي أي قيمة أخرى، n، يساوي n مضروباً بعاملي n-1. إذاً 3! هو !2 × 3، و!2 هو !1 ×2، و!1 هو !0 × 1. بوضعها جميعاً معاً، نحصل على أن !3 يساوي 1 × 1 × 2 × 3، يساوي 6.
إذا كنت تستطيع كتابة تعريف تعاودي لشيء ما، يمكنك عادة كتابة برنامج في Java لحسابه. الخطوة الأولى هي تحديد معاملات هذا التابع، ونوع القيمة التي يرجعها. مع قليل من التفكير، يجب أن تستنتج أن التابع العاملي يأخذ عدداً صحيحاً واحداً كمعامل ويرجع قيمة صحيحة:

public static int factorial (int n) {
}
إذا تصادف أن يكون المتحول صفراً، كل ما علينا فعله هو إرجاع القيمة 1:
public static int factorial (int n) {
  if (n == 0) {
  return 1;
  }
}

وهذه هي الحالة القاعدية.
وإلا، هذا هو الجزء الممتع، علينا عمل استدعاء تعاودي لحساب عاملي n-1، ثم ضربه بn.

public static int factorial (int n) {
  if (n == 0) {
    return 1;
  } else {
    int recurse = factorial (n-1);
    int result = n * recurse;
    return result;
  }
}

لو نظرنا إلى مجرى تنفيذ هذا البرنامج، لوجدناه مشابهاً لـ countdown من القسم 4.8. إذا استدعينا factorial مع القيمة 3:
بما أن 3 ليست صفراً، نتبع الفرع الثاني ونحسب العاملي لـ n-1.
بما أن 2 ليس صفراً، نتبع الفرع الثاني ونحسب العاملي لـ n-1.
بما أن 1 ليست صفراً، نتبع الفرع الثاني ونحسب العاملي لـ n-1.
بما أن 0 هو الصفر، نتبع الفرع الأول ونعيد القيمة 1 فوراً بدون القيام بأية استدعاءات تعاودية أخرى.
يتم ضرب القيمة المعادة (1) بـ n، الذي يساوي 1، وتتم إعادة النتيجة.
يتم ضرب القيمة المعادة (1) بـ n، الذي يساوي 2، وتتم إعادة النتيجة.
يتم ضرب القيمة المعادة (2) بـ n، الذي يساوي 3، وتتم إعادة النتيجة، 6، إلى main، أو أياً كان من استدعى العملية factorial (3).
هنا تجد المخطط الهرمي لهذه السلسلة من استدعاءات العمليات:
http://file.topmaxtech.net/images/ph...3959288451.jpg
يتم إظهار القيم المعادة وهي تمرر عائدة إلى أعلى الهرم.
لاحظ أنه في آخر حالة للعملية factorial، لا يوجد متغيرات محلية باسم recurse أو resultلأنه عندما يكون n=0 لا يتم تنفيذ الفرع الذي ينشئهم.