توابع بازگشتی چطور کار می کنند؟ How does recursion work?

فرض کنید جمعی از افراد ایستادن و قراره کاری توسط همه شون انجام بشه.

بعد یک نفر از وسط جمع می گه من می تونم قسمت اول کار رو انجام بدم، نفر دیگری می گه من می تونم قسمت دوم کار رو انجام بدم، و به همین ترتیب الی آخر. تا اینکه کار کاملا بینشون تقسیم میشه.

حالا در یک مورد عجیب، فرض کنید همون جمع وجود داشته باشه ولی تمام افراد فقط یک نفر باشن! می دونم که خیلی تصورش عجیبه.

حالا مجددا فرض کنید فرار باشه کاری توسط همه شون انجام بشه. طبعا نفر اول وقتی بگه می تونه اون کار رو انجام بده بقیه همه هم می تونن. بنابراین باید اون یک نفر اون کار رو به نحوی انجام بده که کمکی بکنه به بقیه که با انجام دقیقا همون کار مشابه اون فرد حل مشکل رو یک گام به جلوتر ببرن!

یک مثالش x^n هست در شرایطی که فرض کنیم فقط عمل ضرب برامون میسر باشه و نتونیم توان رسانی کنیم.

حالا یک تابع رو تصور کنید که بگه من می تونم ضرب دو عدد رو برگردونم. پس

func pow(int x, int n){

    if(n==2) return x*x;

}

حالا بیاید ببینیم این تابع اگر کار خودشو دوباره انجام بده چی می تونه تولید کنه

func pow(int x, int n){

    if(n==2) return x*x;

    return pow(x,n/2)*pow(x,n/2);

}

دقت کنید این همون تابع بالاست، با این تفاوت که صدا کردن خودش با همون کار "منتهی این بار به شکل تقسیم شده تر" بهش واگذار شده.

حالا اگر بهش بدیم: pow(x,4) اول این اجرا میشه: return pow(x,2)*pow(x,2);

بعد این اجرا میشه: return x*x;

بعد این return x*x

بعد هم این return (x*x)*(x*x);

که همون جواب مورد نظر ماست.

اما حالا بیاید بهش بدیم pow(x,3) اول این اجرا میشه: return pow(x,1)*pow(x,1);

که به وضوح از همین اول غلطه! چراکه توان ما فرد بوده و به یک ضرب اضافی دیگر در x هم احتیاج داریم. حتی ایراد کار تنها به همینجا هم خلاصه نمیشه و حتی وقتی که به اجراش ادامه هم می ده به یک دور بی نهایت دچار میشه چونکه 2 تقسیم بر 2 مساوی 1 میشه درحالیکه ما شرط پایانی رو، برابر شدن توان با 2 در نظر گرفتیم. درحالیکه توان های 1 و صفر کوچکترین توان های غیرمنفی هستن. پس تابع رو مجددا بازنویسی می کنیم:

func pow(int x, int n){

    if(n<0) return -1; //This function is not going to calculate negative powers.

    if(n<=1) return x;

    if(n%2==0) //if n is even

        return pow(x,n/2)*pow(x,n/2);

    return pow(x,n/2)*pow(x,n/2)*x;

}

و حالا این تابع دیگه به درستی کار می کنه.

دقت کنید جمله ی آخر احتیاجی به else نداشتیم چونکه شرط if اگر درست می بود return مقابلش انجام می شد و وقتی انجام نشود به return بعدی می رسد که خود به خود این همین معنای else شدن را دارد با این تفاوت که اندکی از سربار کاری که پردازنده بخواهد انجام بدهد کاسته شده است.

بعد از دیدن فیلم ماحی

یه جورایی خوشحالم که این فیلمو دیدم.

احساسم از دیدن این فیلم اینه که پیش یه عده که یه سری کارها و راه و چاه های پیچیده رو بلدن حتی یه بازیکن ضعیف هم نیستم. یه بازیکن ضعیف حداقل تو بازی حضور داره، حتی اگر می بازه. اما من و امثال من حتی تو زمین بازی هم نیستیم.

البته که این بازی کثیف بود. با اینکه خیلی از روابط و رانت و رابطه بازی ها و پولشویی ها و بده بستون های پیچیده و وحشیش رو نفهمیدم، اما تباهی و "شیطانیت" از همه سر و روش می بارید.

نکته ی جالب این بود که تا یکی رو می باختن روی یه نفر دیگه سرمایه گذاری می کردن یا وقتی یه راه جواب نمی داد سریع تکنیک رو عوض می کردن. از این یه جورایی میشه به نحو درست تو زندگی استفاده کرد.

چیزی که بیشتر از همه توی این فیلم تو ذوق آدم می زد این بود که این آدما با فکرا و نقشه ها و دستوراتشون همه کس و همه چیز رو به بازی می گرفتن  و این وسط تو دائم این حس بهت دست می داد که در مقابلشون حقیری ولی وقتی فکرشو می کنم می بینم آخرش خود اونا هم با مارمولکایی مث خودشون بازی داده می شدن و عملا انگار در مقابل خدا همه ی ما چه پیچیده چه ساده در معرض آزمایش هستیم. پس گول حقارتمون رو نخوریم و مبادا که تصور کنیم گناهان ما هم به خاطر این سونظر حقارت گونه ای که نسبت به خودمون داریم کوچک خواهند بود و درنتیجه فریب بخوریم و اونها رو کم اثر و مجاز بشماریم.

در هر قدرت و توان و جایگاهی که هستیم حق ما و موفقیت ما اینه که لحن نباشیم.