١٥ ديسمبر ٢٠٢١

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

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

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

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

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

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

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

لنبدأ بمثال صغير يوضح الفكرة – دعنا نكتب دالة 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

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

التكرار دائماً أقصر Recursive

الحل المتكرر “Recursive” دائماً أقصر من التكراري “Iterative”.

هنا يمكننا إعادة كتابة pow(x, n) بإستخدام العامل المشروط ? بدلاً من if لنجعلها أكثر اختصاراً و قراءً

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)

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

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

برجاء الملاحظة:

Here in the picture we use the word “line”, as in our example there’s only one subcall in line, but generally a single line of code may contain multiple subcalls, like pow(…) + pow(…) + somethingElse(…).

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

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”. وأحياناً يحتاج إلي تحسين. ولكن في بعض الحالات الحل المتكرر هو أحسن وأسهل كفاية لتستخدمه.

مهمه

الأهمية: 5

أكتب دالة sumTo(n) لحساب مجموع الارقام هكذا numbers 1 + 2 + ... + n.

Write a function sumTo(n) that calculates the sum of numbers 1 + 2 + ... + n.

مثلاً:

sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
sumTo(4) = 4 + 3 + 2 + 1 = 10
...
sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050

أستخدم ثلاث طرق مختلفة:

  1. استخدم حلقة for.
  2. استخدم التكرار (مساعدة: sumTo(n) = n + sumTo(n-1) for n > 1)
  3. استخدم المتتالية العددية.

مثال علي الناتج:

function sumTo(n) { /*... your code ... */ }

alert( sumTo(100) ); // 5050
  1. ما الحل الاسرع؟ وما الابطأ؟ ولماذا؟

  2. نستطيع إستخدام التكرار للعد sumTo(100000)?

الحل بإستخدام الحلقة:

function sumTo(n) {
  let sum = 0;
  for (let i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
}

alert( sumTo(100) );

الحل بإستخدام التكرار:

function sumTo(n) {
  if (n == 1) return 1;
  return n + sumTo(n - 1);
}

alert( sumTo(100) );

الحل بإستخدام هذه المعادلة: sumTo(n) = n*(n+1)/2:

function sumTo(n) {
  return n * (n + 1) / 2;
}

alert( sumTo(100) );
  1. منطقياً حل المعادلة هو أسرع حل لأننا نستخدم ثلاث عمليات فقط لأي رقم n.‘إذا الرياضة تساعد

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

  1. يعض المحركات تدعم تحسين “tail call”: أذا كان النداء المتكرر هو الأخير في الدالة (مثلما فيsumTo ) إذا فالدالة الخارجية لن تحتاج إلي مواصلة التنفيذ وبالتالي فإن المحرك لا يحتاج إلي تذكر سياق التنفيذ. ذلك يزبل العبء عن الذاكرة لذلك العد إلي sumTo(100000) ممكناً. لكن محرك جافا سكريبت لا يدعم هذا التحسين أو المعظم لا يدعم, لذلك سيكون هناك خطأ: لقد تخطيت الحجم الأقصي لكومة سياق التنفيذ.
الأهمية: 4

الـ مضروب هو عدد طبيعي يعتبر حاصل ضرب الرقم في نفس الرقم – 1 ثم في نفسه – 2 وهكذا حتي نصل إلي 1.

مضروب العدد n يكتب رياضياً علي هذا الشكل and so on till 1. The factorial of n is denoted as n!

يمكننا أن نعرفها بهذه الطريقة:

n! = n * (n - 1) * (n - 2) * ...*1

قيم مضروب أرقام مختلفة : للـ n

1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120

المهمة هي أن تكتب دالة factorial(n) التي تقوم بحساب n! بإستخدام الداءات المتكررة.

alert( factorial(5) ); // 120

مساعدة: n! يمكن كتابته علي هذا الشكل n * (n-1)! مثلاً: 3! = 3*2! = 3*2*1! = 6

By definition, a factorial n! can be written as n * (n-1)!.

الحل يكمن في التعريف n! يساوي n * (n-1).

بطريقة أخري, ناتج factorial(n) يمكن أن نحسبه علي هذه الطريقة n مضروب في ناتج factorial(n-1). ومناداة n-1 يمكن أن تنادي نفسها بتكرار أصغر فأصغر حتي نصل إلي1

function factorial(n) {
  return n != 1 ? n * factorial(n - 1) : 1;
}

alert(factorial(5)); // 120

الاساس التكراري هنا هو 1 يمكن أيضاً ان يكون 0 ولكن هذا لا يهم هذا يعطينا مناداة إضافية فقط:

function factorial(n) {
  return n ? n * factorial(n - 1) : 1;
}

alert(factorial(5)); // 120
الأهمية: 5

متسلسلة فيبوناتشي لها قانون Fn = Fn-1 + Fn-2. أو بمعني أخر الرقم القادم يساوي مجموع الرقمين الذان يسبقانه

أول رقمين هما 1 ثم 2(1+1) ثم 3(1+2) ثم 5(2+3) وهكذا: 1, 1, 2, 3, 5, 8, 13, 21....

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

أكتب دالة fib(n) تُعطيك n-th العدد الموجود في هذا الترتيب

مثلاً:

function fib(n) { /* your code */ }

alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757

ملحوظة: الدالة يجب أن تكون سريعة. نداء fib(77) يجب ألا يأخذ أكثر من أجزاء من الثانية

الحل الأول الذي مكن تجربته هنا هو الحل المتكرر.

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

function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // will be extremely slow!

لكن القيم الكبيرة من الـ n سيكون بطئ جداً مثلاً fib(77) يمكن أن تعطل المحركلمد من الزمن

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

مثلاً لنري قطعة من حساب fib(5):

...
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
...

fib(5) و fib(4) كلاهما يحتاج لحساب fib(3) إذن هذا الدالة سوف تنادي مراتان ليس لهما علاقة ببعضهما.

ها هي صورة كاملة لشجرة التكرار:

واضح هنا أن fib(3) تمت مناداتها مرتين و fib(2) سيتم مناداتها وتنفيذها ثلاث مرات. لذلك سيكون عدد الدوال التي تم تنفيذها سيكون هائل جداً حتي إذا كان n=77.

يمكننا تحسين هذا عن طريق تذكر القيم التي تم حسابها من قبل: مثلاإذا وجدنا fib(3) تم حسابها من قبل نأتي بقيمتها فوراً ولا نقوم بتنفيذها مرة أخري

ذلك يضع أمامنا خيار أخر وهو أن نتخلي عن التكرار واستخدام طريقة حل مبنية علي الـ Array مختلفة تماماً

بدلاً من أن نذهب من n أسفل للقيم الأقل, يمكن أن نصنع حلقة تبدأ من 1 و 2, ثم نأتي بـ fib(3) بأعتبار أن ناتجها هو مجموعهم, ثم fib(4) بأعتبار أن ناتجها مجموع القيماتان السابقان ثم fib(5) تذهب لأعلي ثم أعلي حتي تصل إلي القيمة المطلوبة. كل ما نحتاج تذكره هو الرقمين السابقين.

هنا سنشرح الخطوات للخوارزمية الجديدة بالتفصيل.

في البداية:

// a = fib(1), b = fib(2), these values are by definition 1
let a = 1, b = 1;

// get c = fib(3) as their sum
let c = a + b;

/* we now have fib(1), fib(2), fib(3)
a  b  c
1, 1, 2
*/

الأن نحن نريد الحصول علي fib(4) = fib(2) + fib(3).

الأن نحتاج إلي تبديل المتغيرات a,b سيصبحوا fib(2),fib(3) و c سيكون مجموعهم :

a = b; // now a = fib(2)
b = c; // now b = fib(3)
c = a + b; // c = fib(4)

/* now we have the sequence:
   a  b  c
1, 1, 2, 3
*/

الخطوة التالية تعطينا تسلسل أخر للأرقام:

a = b; // now a = fib(3)
b = c; // now b = fib(4)
c = a + b; // c = fib(5)

/* now the sequence is (one more number):
      a  b  c
1, 1, 2, 3, 5
*/

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

الكود كاملاً:

function fib(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

الحلقة تبدأ من i=3, لأننا نعرف قيمة العددين الأولين a=1, b=1.

هذا الحل يسمي البرمجة الديناميكية.

الأهمية: 5

هذه هي القائمة المتصلة كما ذكرناها في هذا الفصل التكرار و الحزمة:

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

إكتب دالة printList(list) التي تقوم بطباعة القائمة واحداً تلو الأخر.

قم بحلها بطريقتين:

  1. مرة بإستخدام الحلقة:
  2. مرة بإستخدام التكرار:

ماهو الأفضل: بالتكرار أم بدون التكرار؟

حل مبني علي الحلقة

الحل:

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

function printList(list) {
  let tmp = list;

  while (tmp) {
    alert(tmp.value);
    tmp = tmp.next;
  }

}

printList(list);

يرجي ملاحظة أننا نستخدم المتغير المؤقت tmp للمرور خلال القائمة. من الناحية الفنية, يمكن أن نستخدم عامل الدالة list:

function printList(list) {

  while(list) {
    alert(list.value);
    list = list.next;
  }

}

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

لو غيرنا الـ list سنخسر هذه الميزة.

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

علي صعيد أخر, دور tmp يهتم فقط بالانتقال بين عناصر القائمة, مثل i الموجود في حلقة for

From the other side, the role of tmp is exclusively a list traversal, like i in the for loop.

الحل التكراري

الحل التكراري للدالة printList(list) يتبع منطق بسيط لطباعة القائمة: يجب طباعة العنصر الحالي list ثم إعادة الموضوع للباقي list.next حتي تنتهي القائمة :

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

function printList(list) {

  alert(list.value); // output the current item

  if (list.next) {
    printList(list.next); // do the same for the rest of the list
  }

}

printList(list);

الأن من هو الأفضل؟

عملياً الحلقة أكثر كفاءة بالرغم من أنهم يقومون بنفس المهمة, لكن الحلقة لا تستطيع عمل أكثر من نداء متداخل.

علي الجانب الأخر التكرار يعتبر أسهل للفهم وأقصر

الأهمية: 5

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

بطريقتين :

  1. بإستخدام الحلقة
  2. بإستخدام التكرار

حل التكرار

منطق التكرار هنا يعتبر مخادع قليلاً.

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

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

function printReverseList(list) {

  if (list.next) {
    printReverseList(list.next);
  }

  alert(list.value);
}

printReverseList(list);

حل الحلقة

حل الحلقة هو الاخر يعتبر معقد قليلاً بالنسبة إلي الطباعة المباشرة.

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

إذا ماذا نفعل؟ نستطيع أولاً أن نمر خلال العناصر بالطريقة المباشرة ونتذكرهم عن طريق تخزينهم في ترتيب Array, ثم نطبع الترتيب الذي تذكرناه ولكن بشكل عكسي:

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

function printReverseList(list) {
  let arr = [];
  let tmp = list;

  while (tmp) {
    arr.push(tmp.value);
    tmp = tmp.next;
  }

  for (let i = arr.length - 1; i >= 0; i--) {
    alert( arr[i] );
  }
}

printReverseList(list);

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

خريطة الدورة التعليمية