كم مرة نادت ال recursive function نفسها ؟

السلام عليكم و رحمة الله تعالى و بركاته

لنفرض أنك تقوم بكتابة recursive function تقوم بإستدعاء نفسها عدد معين من المرات بناءا على العبارات التى تستقبلها لحساب الناتج ، مثلا يقال ان الوظيفه Fibonacci لكى تحسب ال Fibonacci number للعد 20 فإنها تنادى نفسها 21 الف و 890 مرة خخخخخ ، و يقال ان الوظيفة Factorial لكى تحسب ال factorial number للعدد 20 فإنها تنادى نفسها 20 مرة ، بما ان هذه الوظائف Idempotent اى ان الناتج لا يتغير مادام العبارات ثابتة يمكننا اخضاعها ل optimization pattern مثل ال Memoization لتقليل هذا العدد الهائل من المرات التى تنادى بها نفسها ، هذا موضوع المقال القادم إن شاء الله ، لكن هذا الموضوع عن معرفة العدد الذى تنادى به ال recursive function نفسها ، هذه المعلومة تهمنى للغاية لأنى أقوم بكتابة بعض ال Benchmarks لوظائف recursive ، يمكنك معرفة ذلك من خلال profiler او debugger فى المتصفح او IDE مثل Aptana Studio على سبيل المثال ، لكنى بعد العديد من المحاولات كتبت وظيفه howMany تقوم بحساب عدد المرات التى تنادى الوظيفة ال recursive نفسها بناءا على طريقة عمل Alias Chaining فى لغة البرمجة Ruby تم تعديل الكود ، الكود التالى يوضح الوظيفه Fibonacci :

function fibonacci(n){
    if(n<2) return n;
    return fibonacci(n-1) + fibonacci(n-2);
};

fibonacci(10); //55
fibonacci(13); //233

و عن طريق الوظيفة howMany يمكننا حساب عدد المرات التى تنادى فيها الوظيفة fibonnaci نفسها لتحسب ال fibonacci number للعدد 10 و 13 ، الوظيفة howMany تقبل العبارة الاولى لها recursive function و باقى العبارت هى العبارت التى ستمرر لهذه ال recursive function كما يلى :

howMany(fibonacci, 10); //call itself 176 times
howMany(fibonacci, 13); //call itself 752 times
howMany(fibonacci, 20); //call itself 21,890 times

كما ترى تمكننا من حساب كم مرة تنادى الوظيفة fibonacci نفسها ، و يمكننا تطبيق المثال السابق على اى وظيفة اخرى .

مميزات howMany :
تقوم بحساب عدد المرات التى تنادى ال recursive function نفسها دون الحاجة إلى تشغيل ال debugger او ال profiler فى كل مرة للحاجة لمعرفة ذلك ، و عليه يمكن دمجها فى test suits المكتوب بجافاسكربت .

عيوب howMany :
لا يمكنها حساب عدد المرات التى تنادى فيها ال recursive function نفسها إذا كانت anonymous او كانت ناتجة عن closure .

الكود الخاص ب howMany :

function howMany(fn){
    howMany.__times__ = 0;
    var args = Array.slice(arguments, 1),
    fnStr = fn.toString();
    if(fnStr.indexOf("++howMany.__times__;") < 0){
            eval(fn.name + " = " + fnStr.replace(/\{/, "{++howMany.__times__;"));
    }
    fn.apply(null, args);
    return howMany.__times__;
};

فى الموضوع القادم سأستخدم howMany لمقارنة المرات التى نادت ال recursive function نفسها قبل و بعد تطبيق ال optimization patterns عليها .

About these ads

الأوسمة: function, functional programming, javascript, performance