Posts Tagged ‘recursion’

إجراء عملية تراجعيا

2010/05/14
نحتاج أحيانا إلى القيام بعمل ما على شيء ما يقتضي تنفيذه القيام به نفسه على شيء آخر … حتى نصل لحد يتوقف فيه العمل، عند وجود حالات مشابهة يمكن تحديد كيف يتم العمل على شيء واحد ثم إعادة طلب هذا العمل على الشيء الجديد أثناء تنفيذ العمل الحالي.
لو أخذنا مثال تنظيف درج، العمل هنا هو تنظيف درجة من الدرج، فإذا كان العمل معرف بالشكل التالي (طبعا تنظيف الدرج يتم من الأعلى إلى الأدنى):

إذا كان هناك درجة أعلى من الدرجة الحالية نظفها ثم نظّف الدرجة الحالية.

يأتي الشخص الذي سيقوم بالتنظيف، يقف عند أول درجة ليبدأ بتنفيذ العمل فينظر هل هناك درجة أعلى منها؟ فيجد ، فيقول سأنظف الدرجة الأعلى ثم أعود لهذه بعد ذلك، ينتقل للدرجة الأعلى لينظفها فيقرأ التعليمة، إذا كان هناك واحدة أعلى نظفها ثم عد و نظف الدرجة الحالية … حتى يصل للدرجة الأعلى في الدرج فلا يجد فوقها درجات، فينظفها و ينظف ما تحتها تراجعيا.
هذه الفكرة إذا أردنا أن نستفيد منها برمجيا، سأتحدث عن مثالين:

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

(لدينا قاعدة بيانات تحوي جدولا اسمه cats فيه الحقول: رقم الفئة catid، اسم الفئة cname، و رقم الفئة الأب cparent. نعرف تابعا له الشكل:

function getCats($id){
    $q = mysql_query(“select * from cats where cparent=’$id‘”);
    if(mysql_num_rows($q)>0){
        print “<ul>\n”;
        for($i=0;$i<mysql_num_rows($q);$i++){
            print “<li>”.mysql_result($q,$i,“cname”).“</li>\n”;
            getCats(mysql_result($q,$i,“cid”));
        }
        print “</ul>\n”;
    }
}
getCats(0);

المثال الثاني هو عن الحذف، أيضا، لو كان هناك أقسام تحوي أقسم تحوي أقسام … و كل قسم قد يحوي محتويات، عند حذف قسم يتم حذف كل المحتويات ضمنه إضافة إلى حذف الأقسام الفرعية التي تُحذف بنفس الآلية حتى نصل إلى الأقسام التي لا تحوي أقساما فرعية.
المثال برمجيا يُكتب بالشكل:

احذف (س)
بدء
احذف جميع المحتويات في القسم س
أحضر أرقام الأقسام الفرعية من القسم س و من أجل كل منها: احذف (رقم القسم الفرعي).
انتهاء

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

Advertisements

فكر تعاودي

2008/12/22

غالبا ما يتم التنقل من موضوع لآخر عند وجود أشخاص يتحادثون(شخص واحد على الأقل) يحدث هذا التحول في موضوع الحديث بسبب ورود فكرة تحوي من الأهمية، في رأي أحد المتحادثين على الأقل، ما يفوق أهمية الموضوع الحالي فما إن ترد تلك الفكرة حتى ينتقل إليها، أحيانا يكون الموضوع الجديد محدودا فينتهي الحديث حوله خلال مدة قصيرة ثم يعود الموضوع السابق، و أحيانا يولّد هذا الموضوع بدوره موضوعا آخرا … و هذا ما يسبب في الأوقات القادمة قول أحدهم : وين كنّا ؟؟ متسائلا.
أما كيف تأتي هذه المواضيع رغم “عدم علاقتها” (كما يبدو) ،في بادئ الأمر، بالموضوع الحالي فسأتحدث عن فكرتين، أو بالأصح عن شخصين، الأول هو من قام بتغيير الموضوع و الثاني لاحظَ نقطة تغير الموضوع و يفضل أن يملك تفكيرا تعاوديا جيدا:
بالنسبة لمن قام بتغيير الموضوع فهو عرضت له كلمة أو عبارة أو ربما مشهد أو صوت أو رائحة أو … ضمن موضوعي هذا قد لا علاقة هناك للروائح أو المناظر باحتمال كبير، المهم أن شيئا ما حدث و قد ذكّره هذا الشيء بموضوع أو شخص أو لنقل شيئا آخر بعيدا كل البعد عن الموضوع من وجهة نظر شخص لا يعني له الموضوعان ما يعنياه بالنسبة لمن غيّر الموضوع، هنا أوقف هذا الشخص سير الحديث بالموضوع الحالي و انتقل للموضوع الجديد عندما أتيحت له الفرصة لهذا الفعل (بعض الناس يقطعون حديثك بشكل غبي و البعض ينتظرك لتنهي الحديث و هناك من يهمّ بمقاطعتك فيدرك أنه ارتكب حمقا فيتراجع و هنا تدرك بأن لا أهمية للاستمرار [طويلا] بالموضوع الحالي و أن من المستحسن ترك المجال لهذا المقاطع ليبدأ بموضوعه).
إذن، ما يهمنا حاليا هو أن شيئا ما استدعى شيئا آخر، الشيئان من النظر بشكل عام لا علاقة لهما، إلا أن هناك علاقة لولاها لما استدعى أحدهما الآخر، مما يقودنا إلى فكرة هامة ألا و هي أن هناك ترابط بين الأفكار في ذاكرتنا و أن لهذا الترابط كبير الأهمية لبقاء هذه الأفكار فالفكرة التي لا يبقى أفكار ترتبط بها تفنى أغلب الظن (كما أظن)، لاحظ أنه في لغات البرمجة، و لتكن لغة جافا، أننا غير مضطرين لتدمير الكائنات عندما ننتهي من استخدامها، هناك من يقوم بذلك ولا أريد أن أدخل بالتفاصيل فقط ما أريد أن أذكره هو أن في اللغة شيئا ما مهمته تدمير الكائنات عندما ننتهي من استخدامها، أما كيف يعرف بأننا انتهينا من استخدامها فهذا شبيه بالفكرة التي في ذاكرتنا و التي لم تعد أية فكرة أخرى ترتبط بها (هناك الكثير من الأحداث التي تتلاشى من ذاكرتنا لعدم ارتباطها بأحداث أخرى، مثلا عندما تشتري كيلو موز من دكان …).
هناك متانة في تلك الأفكار التي تحاكي في تحقيقها تصميم الإنسان أو بشكل أعم، ما خلقه الله.

أنتقل للشخص الآخر، ذلك الذي لاحظ أن الآخر غيّر مسار تفكيره بشكل مثير للدهشة! ، كأن تكون تتحدث مع زميل لك حول إحدى المواد في الجامعة و أنتما أمام مكتبة فيقول لك في منتصف حديثك بأن السرطان منتشر بشكل مخيف هذه الأيام ! (سأذكر هذا المثال بعد قليل).
هذا الشخص عندما لاحظ تبدل الحديث حاول أن يعرف ما الذي دعا الآخر ليغير حديثه، عمليا هو يحاول أن يجد ذلك الرابط بين الموضوعين، و هنا قد يفلح و قد لا يفلح و ذلك يعود لعدة عوامل منها أو أهمها هو وجود مواضيع في ذاكرة الآخر ،تشكل مرحلة من مراحل الارتباط بين الموضوعين، لا يعرفها و لم ينجح في تخمينها.
فكيف يحاول معرفة الارتباط ؟ مبدئيا يبحث عن شيء مرتبط بالموضوعين فإن وجد ذلك الشيء فهذا يدل على ارتباط مباشر بين الموضوعين أما إن لم يجده فيحاول (و دون أن يقصد ربما) أن يجد موضوعا ثالثا يربط الموضوعين بمعنى أن هناك ارتباط بين الموضوع الثالث و كل من الموضوعين الآخرين، علما أن لا علاقة لهما ببعضهما دونه، أيضا قد يفلح و … إلى أن يتعب أو يعرف و هذا حسب قوة دماغه.
العودية أو الاستدعاء الذاتي هو مفهوم رياضي يطبّق برمجيا يقول: إن بإمكان تابع أن يستدعي ذاته ضمن ذاته، مثلا لنأخذ مثالا بسيطا رياضيا قبل أن آخذ مثالا حياتيا:
قوة العدد x من الدرجة n تساوي قوة العدد x من الدرجة n-1 مضروبا بـ x، لاحظ بأن عبارة “قوة العدد” وردت في تعريف عبارة “قوة العدد”، و هكذا فإن :

xn = xn-1*x
xn-1 = xn-2*x
xn-2 = xn-3*x

أي

xn = ((((...xn-(n-1))*x)*x)*x)*...x

و هذا ما نعبر عنه بأسلوب آخر عن تعريف xn بقولنا هي x*x*x… عدد n من المرات.

مثال حياتي: كم سعر 5 كيلو من البطاطا ؟ هو سعر 4 كيلو + سعر 1 كيلو، طيب و ما سعر الـ 4 كيلو ؟ هو سعر 3 كيلو + سعر 1 كيلو ، و ما سعر الـ 3 كيلو ؟ هو سعر 2 كيلو + سعر كيلو، و ما سعر 2 كيلو ؟ هو سعر 1 كيلو + سعر 1 كيلو. بعد هذا لن نسأل كم سعر الكيلو إذ أن هناك قيمة أولى يتم التراجع عوديا عند الوصول إليها.
نقوم بتنفيذ الأسلوب التعادي دون أن نفكر بذلك، مثلا قد يحدث أنه كم عمر يوسف؟ فيجيب الآخر بأن يوسف أكبر من زينة بـ 3 سنوات، فيُسأل: كم عمر زينة ؟ 22 سنة فيستنتج السائل بأن يوسف عمره 25 سنة، و قد لا يرغب بمعرفة عمر يوسف بعد أن تصل سلسلة الارتباطات بين أعمار آخرين حدا مملاً.

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

الموضوع بكليته هو رأيي أو لأقل هو ما أظنه أنه. الأفكار كثيرة… أكتفي هنا