Recursive Function چیست و چگونه یک تابع بازگشتی با استفاده از JS پیاده‎سازی کنیم؟

Recursive Function چیست و چگونه یک تابع بازگشتی با استفاده از JS پیاده‎سازی کنیم؟

فرض کنید وارد صف نانوایی می‌شوید و دو نفر در صف هستند. شما از قیمت نان خبر ندارید و از نفر آخر قیمت را جویا می‌شوید اما او نیز مانند شما است و قیمت نان را نمی‌داند و برای کمک به شما از نفر جلویی، یعنی نفر اولِ صف، قیمت را می‌پرسد که متوجه می‏‌شود او هم از قیمت نان اطلاعی ندارد! از آنجا که نفر اول به نانوا نزدیک است، می‌تواند قیمت را از وی جویا شود چرا که مسلماً نانوا از قیمت باخبر است و از همین روی نفر اول از این طریق از قیمت نان اطلاع پیدا کرده و جواب سؤال نفر دوم صف را می‌دهد و او نیز قیمت نان را به اطلاع شما می‌رساند.

مثالی که زده شد در واقع استفاده از Recursion یا به عبارت دیگر استفاده از یک روش Recursive (بازگشتی) برای حل مسأله بود که در اینجا پیدا کردن قیمت نان است و همان‌طور که در مثال بالا متوجه شدید، استفاده از روش ریکرسیو برای پیدا کردن جواب یا حل یک مسأله فقط در دنیای ریاضیات و علوم کامپیوتر به کار نمی‌آید بلکه خیلی اوقات ناخودآگاه در زندگی روزمره نیز از این متد برای حل مسائل ریز و درشت استفاده می‌کنیم. در همین راستا و در ادامۀ این مقاله قصد داریم تا ببینیم تابع بازگشتی چیست و چگونه برای حل مسائل مختلف می‌توانیم از آن استفاده کنیم.

Recursive Function (تابع بازگشتی) چیست؟
در یک تعریف ساده از این اصطلاح باید گفت که اگر در تعریف بدنۀ یک فانکشن خودش را فراخوانی کنیم، یک فانکشن ریکرسیو نوشته‌ایم به طوری که داریم:

function doSomething(n) {
    // statements
    doSomething(n-1);
}

در کد بالا یک الگوریتم ریکرسیو فرضی در فانکشن (doSomething(n پیاده‌سازی شده است چرا که در تعریف بدنۀ فانکشن خودِ تابع (doSomething(n-1 فراخوانی شده است.

در پاسخ به این پرسش که «چرا این کار را انجام می‌دهیم؟» باید گفت در یک حالت خاص از مسأله که می‌توان آن را حالت ابتدایی نامید، پیدا کردن جواب مسأله به سادگی امکان‌پذیر است و به عبارت دیگر به دست آوردن جواب در آن حالت خاص نیازی به محاسبات پیچیده ندارد. همچنین جواب مسأله در همۀ حالت‌ها زنجیروار به یکدیگر ارتباط دارند به نحوی که با شروع از حالت ابتدایی می‌توانیم جواب مسأله را در بقیۀ حالت‌ها پیدا کنیم (مثال نانوایی را به خاطر بیاورید که نفر اول چون در سَر صف است می‌تواند به راحتی از نانوا قیمت نان را بپرسد که این در واقع همان حالت ابتدایی است و بقیه افراد در صف هم به واسطهٔ نفر جلویی یک زنجیره تشکیل می‌دهند که به نفر اول ختم می‌شود و از این طریق می‌توانند از قیمت نان اطلاع کسب کنند.)

برای اینکه بدانید در فانکشن ریکرسیو وقتی به نقطه‌ای می‌رسیم که خودِ فانکشن صدا زده شده است چه اتفاقی می‌افتد، باز هم به مثال نانوایی مراجعه می‌کنیم. نفر سوم وقتی از نفر دوم سؤال می‌پرسد منتظر می‌ماند تا جواب سؤالش مشخص شود و به همین ترتیب نفر دوم نیز وقتی از نفر اول پرسش می‌کند منتظر پاسخ می‌ماند. دقیقاً در فراخوانی توابع بازگشتی نیز همین اتفاق می‌افتد و فانکشن مد نظر در اصطلاحاً Call Stack منتظر جواب می‌ماند (کال استک در واقع یک حافظه جهت نگهداری اطلاعات فانکشن‌هایی است که در یک برنامه فراخوانی شده‌اند ولی اجرای آن‌ها کامل نشده است. این حافظه به صورت استک است یعنی ترتیب ورود داده‌ها بر خلاف ترتیب خروج‌شان است که برای آشنایی با مفهوم استک می‌توانید به مقالۀ درآمدی بر ساختمان داده در زبان PHP و آشنایی با مفاهیم Stack و Queue مراجعه کنید.)

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

برای درک بهتر این موضوع، مجدد مثال نانوایی را به یاد بیاورید و فرض کنید که یک صف نامحدود از افرادی که قیمت نان را نمی‌دانند وجود داشت و نفر سوم از نفر چهارم قیمت نان را می‌پرسید و نفر چهارم از نفر پنجم و به همین ترتیب پرسش ادامه پیدا می‌کرد که در چنین شرایطی چون مدام از نانوا که قیمت نان را می‌داند فاصله می‌گیریم، نفرات انتهای صف هرگز به جواب نمی‌رسند. بنابراین نحوۀ مناسب فراخوانی یک تابع بازگشتی و به عبارتی گام‌هایی که برای حل مسأله برمی‌داریم (پرسش از نفر جلویی در صف نانوایی به جای پرسش از نفر پشت سر) و همچنین وجود داشتن یک حالت ابتدایی (نفر اول که بتواند از نانوا بپرسد) به ما کمک می‌کند تا بی‌نهایت منتظر نمانده و پس از مدتی به جواب برسیم.

حال این مفاهیم را در نظر داشته باشید تا در ادامۀ مقاله چند مسأله را مطرح کنیم و در هر مسأله پس از پیدا کردن یک الگوریتم ریکرسیو برای حل آن، با استفاده از زبان جاوااسکریپت کد فانکشن ریکرسیو مربوط به آن را ارائه نماییم.

الگوریتم ریکرسیو و عملیات ریاضی بر روی اعداد
در ادامه قصد داریم فانکشن ریکرسیوی بنویسیم که متغیر num را به عنوان ورودی گرفته و حاصل جمع اعداد 1 تا num را محاسبه می‌کند (مثلاً اگر num مساوی با 4 باشد، خروجی فانکشن برابر با 10 است چرا که حاصل 1+2+3+4 برابر با 10 می‌شود.) اگر بخواهیم یک حالت ابتدایی در این مسأله در نظر بگیریم، حالتی است که num برابر با عدد 1 باشد که در این حالت جواب مسأله عدد 1 است.

همان‌طور که پیش از این گفتیم، پس از پیدا کردن حالت ابتدایی باید قدم‌های ریکرسیو را طوری برداریم که به این حالت نزدیک شویم و در این مثال اگر فانکشن خودش را برای محاسبۀ num-1 صدا بزند، با فرض اینکه num > 1 پس از num - 1 بار فراخوانی، به حالت ابتدایی می‌رسیم. برای درک بهتر موضوع، همان مثال num = 4 را در نظر بگیرید که پس از فراخوانی (4)sum ابتدا (3)sum سپس (2)sum و در نهایت (1)sum فراخوانی می‌شود که حالت ابتدایی شامل جواب بدیهی 1 است و دیگر در (1)sum فانکشن (0)sum فراخوانی نخواهد شد و از این به بعد فانکشن‌هایی که فراخوانی شده‌اند، بر خلاف ترتیب وردشان به استک، از آن خارج می‌شوند.

برای درک بهتر این موضوع، کد مربوط به فانکشن (sum(num با استفاده از زبان جاوااسکریپت ارائه شده است:

function sum(num) {
    if (num === 1) {
        return 1;
    } else {
        return num + sum(num - 1)
    }
}

sum(4); //10

همان‌طور که در کد ارائه‌شده مشاهده می‌نمایید، ابتدا با شرط num === 1 حالت ابتدایی بررسی شده است و اگر در این حالت قرار داشته باشیم، چون جواب مشخص است، عدد 1 ریترن می‌شود و در غیر این صورت در حالت ریکرسیو قرار داریم که فانکشن خودش را با آرگومان num - 1 فراخوانی می‌کند و مقدار num را نیز به آن اضافه می‌کند. در واقع، وقتی حاصل‌جمع اعداد یک تا num - 1 را می‌دانیم، با اضافه کردن مقدار num به آن، حاصل‌جمع اعداد یک تا num را به دست خواهیم آورد و به همین دلیل عبارت (num + sum(num - 1 ریترن می‌شود. به منظور درک بهتر این موضوع، در ادامه مراحل اجرای فانکشن بالا برای حالتی که (4)sum صدا زده می‌شود را آورده‌ایم:

1. (4)sum فراخوانی می‌شود.
2. در فراخوانی (4)sum آیا 4 با 1 برابر است؟ خیر. بنابراین (3)sum فراخوانی می‌شود و (4)sum منتظر جواب (3)sum می‌ماند تا آن را با عدد 4 جمع و ریترن کند.
3. در فراخوانی (3)sum آیا 3 با 1 برابر است؟ خیر. بنابراین (2)sum فراخوانی می‌شود و (3)sum منتظر جواب (sum(2 می‌ماند تا آن را با عدد 3 جمع و ریترن کند.
4. در فراخوانی (2)sum آیا 2 با 1 برابر است؟ خیر. بنابراین (1)sum فراخوانی می‌شود و (2)sum منتظر جواب (1)sum می‌ماند تا آن را با عدد 2 جمع و ریترن کند.
5. در فراخوانی (sum(1 آیا 1 با 1 برابر است؟ بله. بنابراین عدد 1 ریترن می‌شود.
6. (2)sum از استک خارج می‌شود و با ادامۀ اجرای (2)sum عدد 2 با (1)sum جمع و حاصل، یعنی عدد 3، ریترن می‌شود.
7. (3)sum از استک خارج می‌شود و با ادامۀ اجرای (3)sum عدد 3 با (2)sum جمع و حاصل، یعنی عدد 6، ریترن می‌شود.
8. (4)sum از استک خارج می‌شود و با ادامۀ اجرای (4)sum عدد 4 با (3)sum جمع و حاصل، یعنی عدد 10، ریترن می‌شود.

مراحل اجرای فانکشن مذکور را به روش دیگری نیز می‌توان ارائه کرد به طوری که داریم:

sum(4)
4 + sum(3)
4 + (3 + sum(2))
4 + (3 + (2 + sum(1)))
4 + (3 + (2 + 1))
4 + (3 + 3)
4 + (6)
10

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

الگوریتم ریکرسیو و انجام عملیات بر روی اعضای آرایه‌ها
انجام عملیات بر روی اعضای یک آرایه نیز می‌تواند به روش ریکرسیو و با فرایندی شبیه به آنچه در قسمت قبل توضیح داده شد انجام شود. در انجام عمل جمع بر روی اعداد 1 تا num آن‌قدر مقدار متغیر num را یک واحد کاهش دادیم تا به عدد 1 برسیم و به همین صورت، در یک آرایه هم می‌توانیم آن‌قدر اندازۀ آن را کاهش می‌دهیم تا در نهایت به یک آرایهٔ خالی برسیم.

برای مثال، فرض کنید که فانکشنی به نام (sum(list داریم که قرار است حاصل‌جمع همۀ اعضای list را محاسبه و ریترن کند که برای پیاده‌سازی این مسأله نیز باید حالت ابتدایی و قدم‌های ریکرسیو را مشخص کنیم. حالت ابتدایی در این مسأله وقتی اتفاق می‌افتد که list خالی باشد و در این حالت بدیهی است که حاصل‌جمع اعضای list عدد 0 است چرا که اساساً عضوی در آن وجود ندارد و برای اینکه به حالت ابتدایی نزدیک شویم نیز باید هر بار list را کوچک‌تر کنیم. در واقع، می‌توانیم یکی از اعضای آرایه (مثلاً عضو اول) را خارج کرده و حاصل‌جمع آن عدد و خروجی فراخوانی فانکشن با list جدید، که یک عضو کمتر از آرایهٔ قبلی دارد، را به دست بیاوریم که در این صورت با هر فراخوانی، یک عدد از تعداد اعضای آرایه کم می‌شود و در نهایت به آرایه‌ای خالی، یعنی حالت ابتدایی، می‌رسیم.

در ادامه پیاده‌سازی ریکرسیو فانکشن (sum(list آورده شده است که ابتدا لازم است فانکشن (isEmpty(list سپس فانکشن‌های (getFirstElement(list و (removeFirstElement(list توضیح داده شوند که البته از روی نام این فانکشن‌ها نیز می‌توان عملکردشان را حدس زد:

function sum(list) {
    if (isEmpty(list)) {
        return 0;
    } else {
        return getFirstElement(list) + sum(removeFirstElement(list));
    }
}

فانکشن (isEmpty(list مشخص می‌کند که آیا آرایه خالی است یا خیر به این صورت که اگر list عضوی نداشته باشد این فانکشن مقدار true و در غیر این صورت false را ریترن می‌کند. فانکشن (removeFirstElement(list عضو اول از list را حذف و list جدید را ریترن می‌کند (مثلاً اگر [list = [2, 3, 4 باشد، این فانکشن [4, 3] را ریترن می‌کند.) و فانکشن (getFirstElement(list نیز عضو اول list را ریترن می‌کند به طوری که مثلاً اگر [list = [2, 3, 4 باشد، این فانکشن عدد 2 را ریترن می‌کند:

function isEmpty(list) {
    return (list.length === 0);
}

function getFirstElement(list) {
    return list[0];
}

function removeFirstElement(list) {
    newList = [];
    for (i = 1; i < list.length; i++) {
        newList.push(list[i]);
    }
    return newList;
}

با دانستن عملکرد این سه فانکشن تکمیلی، توضیح (sum(list ساده‌تر می‌شود. در خط دوم خالی بودن لیست با استفاده از فانکشن (isEmpty(list بررسی شده‌ است که اگر مقدار true ریترن شود، این بدان معنا است که list خالی می‌باشد و در نتیجه در حالت ابتدایی قرار داریم و نیازی به هیچ‌گونه محاسباتی نداریم و عدد 0 را ریترن می‌کنیم و در غیر این صورت، list حاوی یک یا تعداد بیشتری عضو است و در بلوک else جمع جبری (getFirstElement(list با (sum(removeFirstElement(list یا به عبارتی حاصل‌جمع عضو اول آرایه و خروجی فراخوانی ریکرسیو فانکشن با ورودی جدید (آرایه‌ای که عضو اول list از آن حذف شده است) ریترن می‌شود که این خط از کد همان قدم ریکرسیو است که با هر فراخوانی به دلیل استفاده از فانکشن (removeFirstElement(list ما را به حالت ابتدایی، که همان خالی بودن لیست است، نزدیک‌تر می‌کند.

در ادامه مراحل اجرای فانکشن (sum(list برای حالتی که [list = [1, 2, 3, 4 می‌باشد ارائه شده است:

sum([1, 2, 3, 4])
1 + sum([2, 3, 4])
1 + (2 + sum([3, 4]))
1 + (2 + (3 + sum([4])))
1 + (2 + (3 + (4 + sum([]))))
1 + (2 + (3 + (4 + 0)))
1 + (2 + (3 + 4))
1 + (2 + 7)
1 + 9
10

در خط اول فانکشن ([sum([1, 2, 3, 4 فراخوانی شده است و در خط دوم به خاطر خالی نبودن این آرایه، فانکشن ([sum([2, 3, 4 فراخوانی شده است تا نتیجه‌ای که ریترن می‌کند با عدد 1 جمع شود و از همین روی ([sum([1, 2, 3, 4 در کال استک منتظر می‌ماند تا نتیجۀ ([sum([2, 3, 4 مشخص شود که این فرایند تا خط پنجم ادامه پیدا کرده است و از خط ششم به بعد یکی پس از دیگری فانکشن‌هایی که در کال استک منتظر مانده‌اند از استک خارج می‌شوند و خروجی‌شان ریترن می‌شود و همان‌طور که اشاره شد، در ساختار استک هر دیتایی که ابتدا وارد شود در آخر خارج می‌شود (در اینجا نیز فانکشن ([sum([1, 2, 3, 4 که در ابتدا فراخوانی و وارد به کال استک شده بود در نهایت از استک خارج شده و در آن 9 + 1 محاسبه و عدد 10 ریترن می‌شود.)

الگوریتم ریکرسیو و ساخت آرایهٔ جدید
در قسمت قبل، انجام عملیات بر روی اعضای آرایه را به صورت ریکرسیو پیاده‌سازی کردیم که در این حالت فانکشن ریکرسیو یک عدد را ریترن می‌کرد اما در این قسمت می‌خواهیم مثالی بزنیم که در آن فانکشن ریکرسیو عملیاتی را روی یک آرایه انجام می‌دهد و لیست جدیدی را ریترن می‌کند.

برای درک بهتر این موضوع، تصور کنید قصد داریم یک تابع بازگشتی به نام (remove(item, list بنویسیم که در list به دنبال item می‌گردد و اگر پیدا کرد آن را حذف و یک آرایهٔ جدید که طبعاً یک عضو کمتر از list دارد ریترن می‌کند و اگر هم item در list پیدا نشود، خودِ list ریترن خواهد شد. در اینجا مانند مثال قسمت قبل حالت ابتدایی موقعی است که آرایه خالی باشد. بدیهی است که item در لیست وجود ندارد و خروجی همان list خواهد بود که به عنوان ورودی به فانکشن داده شده است.

نکته‌ای که در این مثال وجود دارد این است که تنها یک حالت ابتدایی نداریم! بلکه یک حالت ابتدایی دیگر این است که اولین عضو از list برابر با item باشد که در چنین شرایطی item را پیدا کرده‌ایم و باید آن را حذف کنیم (به عبارتی، در این حالت بدیهی است که باید عضو اول از list حذف شود و لیست جدیدی که ساخته شده ریترن شود.) حال که حالت‌های ابتدایی مشخص شد، باید به سراغ مرحلهٔ ریکرسیو برویم که قدم به قدم ما را به حالت ابتدایی نزدیک‌تر می‌کند.

اجازه دهید برای توضیح دادن قدم ریکرسیو به سراغ کد برویم به طوری که در ادامه کد مربوط به فانکشن (remove(item, list ارائه شده است:

function remove(item, list) {
    if (isEmpty(list)) {
        return [];
    } else if (isEqual(item, getFirstElement(list))) {
        return removeFirstElement(list);
    } else {
        newList = remove(item, removeFirstElement(list));
        return addItem(getFirstElement(list), newList);
    }
}

remove('c', ['a', 'b', 'c', 'd']); //['a', 'b', 'd']

در این کد علاوه بر فانکشن‌هایی که در مسألهٔ قبل داشتیم، از دو فانکشن دیگر به نام‌های (isEqual(item1, item2 و (addItem(item, list بهره برده‌ایم که پیش از هر چیز این دو فانکشن را معرفی خواهیم کرد:

function addItem(item, list) {
    newList = [];
    newList.push(item);
    for (i = 0; i < list.length; i++) {
        newList.push(list[i]);
    }
    return newList;
}

function isEqual(item1, item2) {
    return (item1 === item2);
}

فانکشن (isEqual(item1, item2 دو آیتم item1 و item2 را با هم مقایسه و در صورت مساوی بودن مقدار true و در غیر این صورت false را ریترن می‌کند و فانکشن (addItem(item, list یک عضو جدید، که همان item است، را به ابتدای list اضافه و آرایهٔ جدید را ریترن می‌کند.

حال با توجه به کارکرد فانکشن‌های مذکور، در ادامه به تفسیر فانکشن (remove(item, list خواهیم پرداخت. داخل شروط if و else if حالت‌های ابتدایی بررسی شده‌اند تا در صورتی که در این حالات قرار داریم خروجی مربوطه ریترن شود. در خط دوم حالت خالی بودن لیست با استفاده از فانکشن (isEmpty(list بررسی شده است که در این صورت یک لیست خالی یا به عبارتی [] ریترن می‌شود و در غیر این صورت با استفاده از فانکشن ((isEqual(item, (getFirstElement(list عضو اولِ list با item مقایسه می‌شود و در صورتی که این دو برابر باشند در یک حالت ابتدایی دیگر که توضیح داده شد قرار داریم که باید عضو اولِ list را حذف کنیم و لیست جدید را ریترن کنیم که این کار با استفاده از دستور (return removeFirstElement(list در خط پنجم انجام می‌شود و اگر هیچ یک از این شرایط (خالی بودن list یا برابری item با عضو اول از list) برقرار نبود، وارد حالت ریکرسیو شده‌ایم که باید قدم بازگشتی برداریم.

در حالت ریکرسیو که در بلوک else قرار گرفته است، ابتدا فراخوانی ریکرسیو را با دستور ((remove(item, removeFirstElement(list انجام می‌دهیم که در این خط تعداد اعضای list که به عنوان آرگومان وارد می‌شود با استفاده از فانکشن (removeFirstElement(list یک عدد کاهش پیدا می‌کند که در نتیجه بالاخره به نقطه‌ای می‌رسیم که یکی از حالت‌های ابتدایی به وجود می‌آید (لیست خالی می‌شود یا اولین عضوِ list برابر با item می‌شود.) و خروجی در متغیری به نام newList قرار می‌گیرد و از آنجا که این متغیر خروجی فانکشن ریکرسیو است، پس یا در یکی از حالت‌های ابتدایی ریترن شده و یا پس از فراخوانی ریکرسیو و با حذف item ریترن خواهد شد که در نتیجه یا یک آرایهٔ خالی است یا آرایه‌ای است که item از آن حذف شده است و از همین روی تنها کاری که باقی مانده این است که آیتم اول list را که در فراخوانی ریکرسیو با استفاده از (removeFirstElement(list حذف کردیم به newList اضافه و لیست جدید را ریترن کنیم.

در ادامه مراحلی که برای فراخوانی (['remove('c', ['a', 'b', 'c', 'd انجام می‌شود نشان داده شده است که در آن حرفِ c از آرایه حذف می‌شود:

remove('c', ['a', 'b', 'c', 'd'])
addItem('a', remove('c', ['b', 'c', 'd']))
addItem('a', addItem('b', remove('c', ['c', 'd'])))
addItem('a', addItem('b', ['d']) 
addItem('a', ['b', 'd'])
['a', 'b', 'd']

در ابتدا فانکشن (['remove('c', ['a', 'b', 'c', 'd به منظور حذف کاراکتر c از لیست کاراکترها فراخوانی شده است و در خط بعد چون در هیچ‌یک از حالت‌های اولیه قرار نداریم (آرایه خالی نیست و اولین عضو آرایه هم با c برابر نیست)، به سراغ حالت ریکرسیو می‌رویم که در این حالت عضو اولِ آرایه که a است خارج و فراخوانی ریکرسیو با لیست جدید ['b', 'c', 'd'] انجام می‌شود. همان‌طور که قبلاً اشاره شد، در این وضعیت (['remove('c', ['a', 'b', 'c', 'd در کال استک منتظر می‌ماند تا نتیجۀ فراخوانی ریکرسیو بعدی که (['remove('c', ['b', 'c', 'd است آماده شود که خروجی آن به عنوان آرگومان دوم فانکشن ()addItem استفاده شده است (در کد جاوااسکریپت قبلی، به منظور خواناتر شدن سورس‌کد، خروجی را در متغیری تحت عنوان newList قرار دادیم سپس آن را به عنوان آرگومان دوم فانکشن ()addItem استفاده نمودیم.)

مرحلۀ بعدی نیز به همین شکل انجام خواهد شد تا اینکه در ادامه در یکی از حالت‌های اولیه (یعنی حالتی که اولین عضو لیست با item که در اینجا کاراکتر c است برابر می‌باشد.) قرار می‌گیریم. از این مرحله به بعد فانکشن‌ها یکی پس از دیگری از استک خارج می‌شوند و در نهایت لیست بدون کاراکتر c ریترن می‌شود.

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

به طور کلی، در هر فانکشن ریکرسیو سه مورد باید رعایت شود. اولین مورد حالت ابتدایی (Base Case) است که در واقع شرط پایان الگوریتم نیز می‌باشد و لازم به یادآوری است که ممکن است در یک مسأله چند حالت ابتدایی داشته باشیم به طوری که در حالت‌های ابتدایی جواب مسأله بدیهی است و نیازی به محاسبات برای پیدا کردن جواب نیست و در این حالت‌ها فانکشن خودش را فراخوانی نمی‌کند بلکه جواب مسأله در آن حالت خاص را ریترن خواهد کرد.

دومین موردی که باید در نظر داشته باشیم گام بازگشتی (Recursive Step) در حالت‌های ریکرسیو (Recursive Case) است. در حالت‌هایی به جز حالت ابتدایی، باید به نحوی خود فانکشن را صدا بزنیم و گام بازگشتی را برداریم که هر بار به حالت ابتدایی نزدیک‌تر شویم که این قدم در مثال محاسبۀ حاصل‌جمع اعداد، کاهش یک واحدی عدد بود تا در نهایت به عدد 1 برسیم و در مثال حذف آیتم از آرایه، حذف عضو اول و کاهش تعداد اعضای آن بود که در نتیجه یا به آرایه‌ای خالی برسیم یا عضو اول از آرایه همان عضوی باشد که به دنبالش می‌گردیم.

نکتۀ دیگر اینکه الگوریتم ریکرسیو مثل یک حلقۀ تکرار است و در واقع هر فانکشنی که به صورت ریکرسیو نوشته می‌شود را می‌توان با استفاده از حلقه‌های تکرار (Loop) نیز نوشت. با توجه به نوع مسأله، گاهی استفاده از فانکشن ریکرسیو به خواناتر شدن و فهم کد کمک می‌کند و از افزایش حجم کد و پیچیده شدن آن نیز می‌کاهد و گاهی اوقات هم ماهیت مسأله ریکرسیو است. مثلاً در این مقاله به یکی دیگر از مقالات سکان آکادمی لینک داده شده است و آن مقاله نیز لینک به مقاله‌های دیگر دارد. اگر فرض کنیم می‌خواهیم ببینیم که آیا لینک‌‌های یک مقاله به یک مقالۀ خاص می‌رسند یا خیر، ماهیت این مسأله ریکرسیو است زیرا هر بار که یک صفحه را باز می‌کنیم باید به دنبال لینک‌هایش بگردیم و مسأله را از نو با صفحۀ جدید آغاز کنیم اما گاهی از ظاهر مسأله امکان حل کردن آن به صورت ریکرسیو وجود ندارد که با تمرین و مطالعه در این زمینه می‌توان این مهارت را پیدا کرد که در پایان می‌توانید برای آشنایی با نحوهٔ پیاده‌سازی توابع بازگشتی به مقالات زیر مراجعه نمایید:

آشنایی با مفهوم Recursive Function و نحوۀ پیاده‌سازی آن در زبان برنامه‌نویسی پایتون
تابع بازگشتی چیست و چگونه آن را در زبان PHP پیاده‌سازی کنیم؟
Recursive Function چیست و چگونه آن را در زبان جاوا پیاده‌سازی کنیم؟

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

از بهترین نوشته‌های کاربران سکان آکادمی در سکان پلاس


online-support-icon