التكرار و الحزمة

حان الوقت لنعود الأن إلي الدوال ونتعمق في دراستها

موضوعنا الأول سيكون التكرار

إن لم تكن جديداً بمجال البرمجة, إذن من المحتمل أنه مألوف بالنسبة لك ويمكنك تخطي هذا الفصل

التكرار هو نمط برمجة مفيد في الحالات التي يمكن فيها تقسيم المهمة بشكل طبيعي إلي عدة مهام من النوع نفسه لكن أبسط أو عندما يمكن تبسيط مهمة ما إلي إجراء سهل بالإضافة إلي بديل أبسط لنفس المهمة أو كما سنرى قريباً, للتعامل مع بنية بيانات معينة

فعندما تقوم إحدى الدوال بحل مهمة ما, يمكن أن تنادي بداخلها دوال أخرى كثيرة. ومن الممكن ايضاً أن تنادي الدالة علي نفسها. ذلك ما يعرف بإسم التكرار.

طريقتان للتفكير

لنبدأ بمثال صغير يوضح الفكرة – دعنا نكتب دالة pow(x, n) التي ترفع x إلي الأوس n, أو بمعني أخر تضرب x في نفسه عدد n من المرات

pow(2, 2) = 4;
pow(2, 3) = 8;
pow(2, 4) = 16;

هناك طريقتان لتحقيق ذلك

1. التفكير التكراري “Iterative”: حلقة for :

   function pow(x, n) {
     let result = 1;
   
     // multiply result by x n times in the loop
     for (let i = 0; i < n; i++) {
       result *= x;
     }
   
     return result;
   }
   
   alert(pow(2, 3)); // 8

2. التفكير المتكرر “Recursive”: تبسيط المهمة وتكرارها :

   ```js run
   function pow(x, n) {
     if (n == 1) {
       return x;
     } else {
       return x * pow(x, n - 1);
     }
   }
   
   alert( pow(2, 3) ); // 8
   ```
   

   يجب ملاحظة كيف أن المتغير المتكرر مختلف جوهرياً

عندما يتم استدعاء pow(x, n), التنفيذ ينقسم إلي فرعين :

              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)

1. إذا كان n == 1, إذن كل شي بديهى. ذلك يسمي قاعدة التكرار, لأنه علي الفور يعطي الحل البديهى : pow(x, 1) تساوي x.

2. فيما عدا ذلك, يمكننا أن نعتبر pow(x, n) أنها x * pow(x, n - 1). في الرياضات, نكتب هذا التعبير علي هذا الشكل xn = x * xn-1. هذا يسمى بـ *خطوة تكرارية* : نحن نحول المهمة إلي مهمة أصغر ( الضرب في x ) و مناداة الدالة بشكل أبسط ( pow بـ قيمة أصغر للـ n ) والخطوة التالية تبسط الدالة أكثر فأكثر حتي تصل n إلي 1.

نستطيع أن نقول أيضاً أن pow تكرر مناداة نفسها حتي تصل n == 1.

على سبيل المثال, لحساب pow(2, 4) المتغير المتكرر يقوم بهذه الخطوات:

1. pow(2, 4) = 2 * pow(2, 3)
2. pow(2, 3) = 2 * pow(2, 2)
3. pow(2, 2) = 2 * pow(2, 1)
4. pow(2, 1) = 2

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

function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}

العدد الأقصي للمنادايات المتداخلة بما فيهم المناداة الأولي يسمي عمق التكرار في حالتنا سيكون n.

الحد الأقصي لعمق التكرار يحدده محرك جافا سكريبت. يمكننا أن نعتمد علي أنه 10000, بعض المحركات تسمح بأكثر من ذلك لكن 100000 غالباً خارج نطاق معظمهم. وهناك تحسينات تلقائية تساعد علي التخفيف من حدة هذا (“tail calls optimizations”), ولكن لم يحصلوا بعد علي الدعم في كل مكان ويعملون في حالات بسيطة فقط.

هذا العيب يحد من تطبيقات التكرار “Recursion”, ولكنه يظل له إنتشار واسع جداً. وهناك العديد من المهام تحتاج طريقة التفكير المتكررة لإعطائك كود أبسط وأسهل.

سياق التنفيذ “Execution context” و الكومة “Stack”

الأن دعونا نفحص كيف تعمل المنادايات المتكررة. وننظر للجانب المحجوب عن عيوننا للدوال

المعلومات التي تخص عملية تنفيذ الدالة تخزن في شئ يدعي سياق التنفيذ.

سياق التنفيذ هو بنية بيانات داخلية تشمل تفاصيل عن تنفيذ الدالة مثل: من أي مكان تمت مناداة هذه الدالة , و القيمة الحالية للمتغير this (نحن لا نستخدمها هنا) و بعض التفاصيل الداخلية الأخرى

كل هذا يبدو مبهماً أليس كذلك.؟ دعنا نبسط الأمر أكثر

مع كل دالة يتم مناداتها يتم صنع سياق تنفيذي خاص بها وينسب لها

لكن عندما يتم مناداة دالة أخري بداخلها, يحدث الأتي:

• يتم إيقاف الدالة الحالية
• السياق التنفيذي لهذه الدالة يتم تخزينه في بنية بيانات خاصة تدعي كومة السايق التنفيذي “execution context stack”
• بدأ تنفيذ الدالة التي تمت مناداتها بداخلها
• بعد إنتهاء الدالة الداخلية من التنفيذ يتم إسترجاع السياق التنفيذي الذي تم تخزينه في الكومة “Stack”, ثم تعود لمواصلة تشغيل الدالة الخارجية من عند نقطة الإيقاف

دعنا الأن نري ماذا حدث أثناء مناداة pow(2, 3)

pow(2, 3)

في بداية مناداة pow(2, 3) السياق التنفيذي سيقوم بتخزين المتغيرات: x = 2, n = 3, وأيضاً سيقوم بتخزين نقطة التنفيذ التي توجد عند السطر 1 للدالة

يمكن رسم ما حدث في هذا الشكل:

• Context: { x: 2, n: 3, at line 1 } pow(2, 3)

That’s when the function starts to execute. The condition n == 1 is falsy, so the flow continues into the second branch of if:

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

alert( pow(2, 3) );

المتغيرات كما هي, لكن السطر تغير لذلك السياق سيكون هكذا:

• Context: { x: 2, n: 3, at line 5 } pow(2, 3)

لحساب x * pow(x, n - 1), نحتاج إلي نداء الدالة مرة أخري ولكن بقيمة أصغر pow(2, 2).

pow(2, 2)

لكي نستطيع القيام بمناداة دالة داخل أخري, يجب علي جافا سكريبت تذكر السياق التنفيذي الحالي وتخزينه في كومة السياق التنفيذي وكل هذا لكي يستطيع المحرك العودة للدالة الخارجية مرة أخري عند الانتهاء من الدالة الداخلية

هنا نحن نادينا نفس الدالة pow, لكن هذا لا يهم لأن الخطوات السابقة سيتم تنفيذها مرة أخرى :

1. السياق الحالي سيتم تخزينه أعلي الكومة
2. سيتم صنع السياق الجديد الخاص بالدالة الداخلية
3. عند الانتهاء من الدالة الداخلية – نستعيد السياق السابق للدالة الخارجية من الكومة ونستكمل تنفيذه

ها هو سياق الكومة عنما نستدعي الدالة pow(2, 2) :

• Context: { x: 2, n: 2, at line 1 } pow(2, 2)
• Context: { x: 2, n: 3, at line 5 } pow(2, 3)

السياق التنفيذي الجديد سيكون أعلي الكومة وجميع السياقات السابق ستكون أسفله

عندما ننتهي من الدالة الداخلية – يكون من السهل إستعادة السياق السابق لأنه يحتفظ بالمتغيرات الخاصة بالدالة و المكان المحدد التي توقفت فيه.

pow(2, 1)

تتكرر العملية مرة أخري: دالة أخرى تتم مناداتها عند السطر 5 و بقيم x=2, n=1.

سياق تنفيذي جديد يتم صنعه, والقديم يضاف إلي أعلي الكومة:

• Context: { x: 2, n: 1, at line 1 } pow(2, 1)
• Context: { x: 2, n: 2, at line 5 } pow(2, 2)
• Context: { x: 2, n: 3, at line 5 } pow(2, 3)

يوجد الأن 2 سياق قدماء و سياق يتم تنفيذه حالياً لـ pow(2, 1).

الخروج

خلال تنفيذ pow(2, 1), وعلي غير العادة, الشرط n == 1 الأن أصبح صحيح, لذلك الفرع الأول if يعمل:

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

لم يعد هناك دوال أخري ليتم مناداتها, لذلك ستنتهي الدالة برجوع 2.

عندما تنتهي الدالة, السياق التنفيذي لها لم يعد له فائدة بعد الأن, لذلك نقوم بحذفها من الذاكرة. ثم نأتي بالسياق السابق من أعلي الكومة :

• Context: { x: 2, n: 2, at line 5 } pow(2, 2)
• Context: { x: 2, n: 3, at line 5 } pow(2, 3)

ثم يعود تنفيذ دالة pow(2, 2). إنها تمتلك ناتج نداء pow(2, 1), لذلك تنتهي هي الاخري بتقدير x * pow(x, n - 1), وتعود بناتج 4.

ثم نأتي بالسياق السابق:

• Context: { x: 2, n: 3, at line 5 } pow(2, 3)

عندما تنتهي أخر دالة, نحصل علي ناتج pow(2, 3) = 8

العمق التكراري في هذه الحالة يكون: 3.

كما هو موضح في الأعلي, العمق التكراري يساوي العدد الأقصي للسياقات الموجودة في الكومة

يجب ملاحظة متطلبات الذاكرة. السياقات تحتاج إلي ذاكرة. في المثال الذي نشرحه, رفع عدد لأوس n يحتاج إلي ذاكرة تكفي لـ n سياق.

طرق الحلول المبنية علي حلقات مثل for,while تعتبر أكثر توفيراً للذاكرة.

function pow(x, n) {
  let result = 1;

  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

التكرار Iterative في دالة powيستخدم سياق تنفيذي واحد و يتغير فيه المتغيرات i و result. وهذا يحتاج إلي ذاكرة صغيرة وثابتة لا تعتمد علي عدد الـ n كما في

أي دالة متكررة “Recursive” يمكن أن نعيد كتابتها بطريقة التكرار “Iterative”.ودائماً ما يكون التكرار بإستخدام الحلقات أكثر كفاءة.

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

الدالة المتكررة “Recursion” تعطيك كود أقصر وأسهل في القراءة. وضع في إعتبارك أن تحقيق الاستخدام الأمثل ليس مطلوباً في كل الحالات في بعض الحالات أنت فقط تريد كود جيداً.

التنقل المتكرر

مثال أخر وتطبيق علي الدالة المتكررة هو التنقل المتكرر “Recursive Traversals”.

تخيل أنك صاحب شركة. وبنية بيانات العاملين بالشركة مخزنة بهذا الشكل:

let company = {
  sales: [
    {
      name: 'John',
      salary: 1000,
    },
    {
      name: 'Alice',
      salary: 1600,
    },
  ],

  development: {
    sites: [
      {
        name: 'Peter',
        salary: 2000,
      },
      {
        name: 'Alex',
        salary: 1800,
      },
    ],

    internals: [
      {
        name: 'Jack',
        salary: 1300,
      },
    ],
  },
};

أو بمعني أخر الشركة لها أقسام

• القسم يمكن أن يحتوي علي ترتيب “Array” للعاملين بهذا القسم, علي سبيل المثال قسم sales يمتلك 2 موظفين: John و Alice.

• أو يمكن تقسيم القسم الواحد إلي عدة أقسام أخري مثل قسم development له فرعان : sites و internals. كل قسم منهم له الموظفين الخاصيين به.

• يمكن أيضا أن يتشعب كل قسم من هذه الأقسام أكثر فأكثر

  مثلاً قسم sites يمكن أن يتشعب في المستقبل إلي فرق مثل siteA و siteB. وهم نفسهم يمكن تقسيهم أكثر فأكثر ويصبح الأمر مثل الشجرة. هذا ليس بالمثال ولكن يجب أن تضعه في حسابك

دعنا نقول الأن أننا نريد دالة تجمع لنا كل الرواتب في هذه البنية. كيف يمكننا فعل ذلك؟

تفكير التكرار “Iterative” في هذه الحالة ليس سهلاً علي الإطلاق, لأن بنية الموظفين ليست بسيطة. قد يخطر ببالك أولاً عمل حلقة for حول company وبداخلها حلقة أخري حول الأقسام الموجودة في المستوي الأول. ولكن في هذه الحالة نحن نحتاج حلقة أخري بالداخل حول المستوي الثاني من الاقسام مثل sites… وأيضاً حلقة رابعة لاقسام القادمة في المستقبل؟ إذا وضعنا ثلاث أو أربع حلقات داخل بعضهم لكي أستطيع التنقل خلال بيانات هذا الشئ سيكون ذلك كابوساً.

إذن دعنا نفكر بطريقة متكررة “Recursion”.

عندما تعطي الدالة قسم لتجمع رواتبه, هناك حالتين محتملتين:

1. إما ان يكون قسم بسيط ليس له فروع ويتكون من ترتيب “Array” من الأشخاص – حينها سنقوم بعمل حلقة تجمع رواتب هذا القسم ببساطة.
2. إما أن يكون قسم معقد يتكون من عدد N أقسام داخلية – حينها نكرر مناداة الدالة عدد N من المرات لنجمع كل قسم داخلي ونأتي بالناتج.

الحالة الأولي هي أساس التكرار, الحالة البديهية, عندما نستلم ترتيب array

الحالة الثانية عندما تستلم الدالة شئ “object”, يعتبر خطوة متكررة. تعتبر هذه الخطوة معقدة ولكن عن طريق التكرار سيتم تقسيم المهمة إلي مهمات أصغر وأبسط حتي هذه المهات يمكن تقسيمها فيما بعض إلي مهمات أكثر تبسيطاً لكن عاجلاً أم أجلاً ستنتهي المهمات عند الحالة الأولي.

طريقة الحل ستكون بسيطة حتي أنك تسطيع قرأتها من الكود وفهمها:

let company = { // the same object, compressed for brevity
  sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 1600 }],
  development: {
    sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],
    internals: [{name: 'Jack', salary: 1300}]
  }
};

// The function to do the job
function sumSalaries(department) {
  if (Array.isArray(department)) { // case (1)
    return department.reduce((prev, current) => prev + current.salary, 0); // sum the array
  } else { // case (2)
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // recursively call for subdepartments, sum the results
    }
    return sum;
  }
}

alert(sumSalaries(company)); // 7700

الكود قصير وسهل الفهم (نرجو ذلك!). هذه هي قوة الدالة المتكررة. هذه الدالة تعمل ايضاً مع أي عدد من التفرعات المتداخلة

ها هو رسم بياني يوضح كيف تتم مناداة الدالة وما بداخلها.

يمكن أن نستشف المبدأ من خلال ما سبق: كل شئ object {...} يعتبر نداء لدالة أخري, بينما كل ترتيب arrays [...] يعتبر أطراف لشجرة التكرار وهذا هو اساس التكرار الذي يعطينا الحل علي الفور.

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

Note that the code uses smart features that we’ve covered before:

• طريقة arr.reduce تم شرحها في فصل توابع المصفوفات (Array methods) للحصول علي مجموع ارقام داخل ترتيب.
• حلقة for(val of Object.values(obj)) للتكرار علي عدد قيم شئ: Object.values ونعطي ترتيب بيهم أو بمعني أخر تحويل قيم الشئ إلي ترتيب Array.

الهياكل المتكررة

هيكل البيانات التكرارية هو هيكل (بنية) يكرر نفسه في أجزاء أصغر منه.

لقد رأينا للتو هذا علي هيكل الشركة.

الشركة القسم يعتبر:

• إما ترتيب Array من الأشخاص.
• أو شئ object يمتلك أقسام أخري

لاكن بالنسبة لمطورين الويب هناك أمثلة أفضل وأشهر بكثير مثل HTML و XML documents.

في وثيقة الـ HTML-tag, HTML يمكن أن يحتوي علي أي شئ من هذه الأشياء:

• جمل نصية.
• تعليقات HTML.
• HTML-tag أخري (التي تحتوي علي جمل نصيةأو تعليقات أو HTML-tag أخري وهكذا )

هذا الهيكل لا يذكرك بشئ؟ نعم أنه هو ثانياً تعريف متكرر.

لكي نفهم أكثر ونتعمق, سنغطي الأن واحدة أخري من هياكل التكرار تدعي القائمة المتصلة “Linked List” التي من الممكن أن تكون بديلة للترتيب Array في بعض الحالات.

القائمة المتصلة

تخيل أننا نريد تخزين قائمة مرتبة من الاشياء objects.

الاختيار الطبيعي سيكون “ترتيب” Array:

let arr = [obj1, obj2, obj3];

لكن هناك مشكلة مع الترتيب. عملية “إضافة عنصر” و “إزالة عنصر” مكلفة جداً. مثلاً عملية arr.unshift(obj) أو arr.shift() يجب علي الترتيب إعادة ترقيم كل العناصر بعد كل عملية منهم وإذا كان الترتيب كبير جداً هذه العمليات ستأخذ وقت.

في الترتيب Array العمليات السهلة فقط هم arr.push/pop. لأنهم لايحتاجوا إلي الترقيم بعدهم لأنك إما تضيف في أخر الترتيب أو تحذف منه.

كبديل أفضل بكثير في حالة الإضافة والإزالة هو هبكل بيانات يسمي بـ القائمة المتصلة .

تعتبر القائمة المتصلة شئ Object يحتوي علي:

• قيمة
• التالي وهذه تعتبر خاصية تشير إلي العنصر التالي للقائمة المتصلة أو null وهذا يعبر نهاية القائمة.

مثلاً:

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null,
      },
    },
  },
};

عرض بياني للقائمة:

كود بديل لصنعها:

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };
list.next.next.next.next = null;

هنا يمكن أن نري بوضح أن هناك عدة أشياء objects, يحتوي كل منهم علي قيمة و التالي الذي يشير إلي ما بعده. المتغير list هو الأول في هذه السلسلة, لذلك إتباع التالي الذي يشير إلي التالي يجعلني أصل إلي نهاية العناصر والقائمة.

يمكن تقسيم القائمة لعدة أجزاء وتجميعهم لاحقاً.

let secondList = list.next.next;
list.next.next = null;

للربط:

list.next.next = secondList;

وبالطبع يمكننا إزالة أو إضافة أي عنصر في أي مكان.

مثلاً كي نضع قيمة جديدة في بداية القائمة, نحتاج إلي تعديل رأس القائمة:

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };

// prepend the new value to the list
list = { value: "new item", next: list };

لحذف قيمة من المنتصف كل ما عليك فعله هة تغير قيمة التالي للعنصر الذي يسبق ما تريد حذفه:

list.next = list.next.next;

نحن جعلنا هنا list.next تتخطي قيمة 1 إلي قيمة 2. الأن قيمة 1 حالياً تم إقصائها من السلسلة. لو هذا االعنصر لم يتم تخزينه في مكان أخر, أذا سيتم مسحه تلقائياً من الذاكرة.

علي عكس الترتيبات Arrays, لا يوجد إعادة ترقيم, نحن نستطيع ببساطة إعادة ترتيب العناصر.

في الطبيعي, القائمة ليست دائماً أحسن من الترتيبات. وإلا كان كل الاشخاص استخدموا القائمة فقط.

الجانب السلبي الرئيسي أنك لا تستطيع الوصول إلي عنصر عن طريق رقمه. في الترتيب هذا سهل: arr[n]. لكن في القائمة نحتاج إلي البدأ من بداية القائمة ونذهب التالي عدد N من مرات لنصل إلي اخر القائمة

لكن لا نحتاج دائماً لمثل هذه العمليات. مثلاً عندما نحتاج أول و أخر عنصر في القائمة إذن يمكن استخدام هيكل البيانات هذا deque – هذا الهيكل يمنحني سرعة إضافة و حذف العناصر من الطرفين, ولكن لا يساعدني في عناصر المنتصف.

بإختصار إذا أردت التعامل أكثر مع عناصر المنتصف استخدم هيكل البيانات القائمة المتصلة إذا اردت التعامل أكثر مع عناصر الطرفين الأول و الأخير استخدم هيكل بيانات الصف

يمكن أيضاً للقوائم أن تتحسن:

• يمكن أن نضيف خاصية أخري تدعي السابق إلي جانب خاصية التالي .التي تشير إلي العنصر السابق لتسهيل الوصول إلي العنصر السابق.
• من الممكن أيضاً إضافة متغير نحتفظ فيه بمكان العنصر الاخير ونسمي هذا المتغير ذيل tail.
• يمكن تعديل الهيكل ليناسب إحتياجاتك

ملخص

بعض التعريفات:

• التكرار “Recursion” : يعتبر تعريف برمجي معناه مناداة الدالة لنفسها. الدالة المتكررة تستخدم لحل المهام بشكل أنيق.

  عندما تنادي الدالة نفسها, هذا يسمي *خطوة متكررة*. الاساس للدالة المتكررة يعتبر أبسط صورة للدالة ولا يمكن مناداة الدالة مرة أخرى ولولا هذا الشرط ستظل الدالة تنادي نفسها إلي ما لا نهاية.
  

• الـ تعريف المتكرر يعتبر هيكل بيانات يعرف نفسه بنفسه عن طريق التكرار.

  مثلاً القائمة المتصلة يمكن تعريفها علي أنها هيكل بيانات تتكون من شئ object يشير إلي القائمة نفسها.

  list = { value, next -> list }

  الشجر مثل عناصر الـ HTML أو الأقسام مثل ما ذكرنا أعلي هذا الفصل.

أي دالة متكررة يمكن كتابتها أيضاً بشكل “Iterative”. وأحياناً يحتاج إلي تحسين. ولكن في بعض الحالات الحل المتكرر هو أحسن وأسهل كفاية لتستخدمه.