بازگشت یا Recursion چیست? برسی توابع بازگشتی در جاوااسکریپت

بازگشت (Recursion) تکنیکی است برای حل مسائل کامپیوتری با ایجاد تابعی که خود را صدا میزند تا به نتیجه دلخواه برسد.

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

بازگشت (Recursion) چیست؟

فرض کنید تابعی داریم که اعداد از 1 تا 5 در کنسول نمایش میدهد:

function log(num){
    if(num > 5){
        return;
    }
    console.log(num);
    log(num + 1);
}

log(1);

وقتی کد بالا را اجرا میکنیم، تابع log خود را تا زمانی که مقدار num کمتر از 5 باشد صدا میزند.

تابع بازگشتی باید حداقل یک شرط داشته باشد تا صدا زدن خود را متوقف کند در غیر این صورت به صدا زدن خود ادامه میدهد تا خطای stack overflow رخ دهد.

شرطی که تابع بازگشتی را از صدا زدن خود منع میکند با عنوان شرط پایه (یا base case) شناخته میشود. در تابع بالا شرط پایه زمانی است که num بزرگتر از 5 باشد.

چرا از حلقه استفاده نمیکنیم؟

هر مسئله ای که با تابع بازگشتی قابل حل باشید یک راه حل دیگر با استفاده از حلقه ها نیز دارد. مثال بالا با حلقه ها این گونه نوشته میشود:

for(let i = 1; i <= 5; i++){
    console.log(i);
}

زبان های مدرن برنامه نویسی مثل جاوا اسکریپت حلقه های for و while را دارند ولی زبان هایی مثل Clojure حلقه ای ندارند و باید از بازگشت در آنها به منظور تکرار اجرای کدی استفاده کرد.

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

برای مثال تابعی داریم که از اعداد بین 1 تا 10 به صورت تصادفی انتخاب می کند و تعداد دفعات اجرای کد تا رسیدن به عدد 5 را در کنسول نمایش می دهد:

function randomUntilFive(result = 0, count = 0){
    if(result === 5){
        console.log(`The random result: ${result}`);
        console.log(`How many times random is executed: ${count}`);
        return;
    }
    result = Math.floor(Math.random() * (10 - 1 + 1) + 1);
    count++;
    randomUntilFive(result, count);
}

randomUntilFive();

کد بالا را نمیتوانیم با حلقه for جایگزین کنیم. ولی میتوان با while جایگزین کرد:

let result = 0;
let count = 0;

while (result !== 5) {
  result = Math.floor(Math.random() * (10 - 1 + 1) + 1);
  count++;
}

console.log(`The random result: ${result}`);
console.log(`How many times random is executed: ${count}`);

به غیر از بعضی سوالات مصاحبه که بنا به درخواست فرد مصاحبه کننده نیازمند حل مسئله با بازگشت است، در بقیه موارد میتوان راه حلی با استفاده از for یا while پیدا کرد.

چگونه تابع بازگشتی را بخوانیم

درک تابع بازگشتی در نگاه اول چندان آسان نیست. مراحل زیر به شما کمک میکنید تا توابع بازگشتی را سریعتر بخوانید و درک کنید:

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

با مثال زیر مراحل بالا را امتحان میکنیم. شرط پایه را در if میتوانید پیدا کنید:

function randomUntilFive(result = 0, count = 0){
    if(result === 5){
        // base case is triggered
    }
    // recursively call the function
}

randomUntilFive();

یعنی این که با دادن عدد 5 به تابع میتوانیم به شرط پایه برسیم:

function randomUntilFive(result = 0, count = 0){
    if(result === 5){
        console.log(`The random result: ${result}`);
        console.log(`How many times random is executed: ${count}`);
        return;
    }
}

randomUntilFive(5);

چون پارامتر count نباید صفر باشد، با دادن عدد 5 به تابع میتواینم مرحله دوم را نیز انجام دهیم.

و در آخر نیاز داریم آرگومانی را پیدا کنیم که با آن تابع ما حداقل یکبار خود را صدا بزند. که در تابع بالا هر عددی به جز 5 یا هیچ (به دلیل وجود مقدار پیش فرض):

function randomUntilFive(result = 0, count = 0){
    if(result === 5){
        console.log(`The random result: ${result}`);
        console.log(`How many times random is executed: ${count}`);
        return;
    }
    result = Math.floor(Math.random() * (10 - 1 + 1) + 1);
    count++;
    randomUntilFive(result, count);
}

randomUntilFive(4); 
// any number other than five 
// will execute the recursive call

و تمام. اکنون فهمیدید که تابع randomUntilFive تا زمانی که result برابر با 5 باشد خود را صدا خواهد زد.

چگونه تابع بازگشتی بنویسیم

نوشتن تابع بازگشتی نیز تقریبا مانند خواندن آن است:

• تابعی معمولی بنویسید که شرط پایه دارد
• آرگومان هایی به تابع بدهید که فورا شرط پایه اجرا شود
• آرگومان بعدی که شرط پایه را اجرا میکند به تابع بدهید

برای مثال وقتی میخواهید تابعی بنویسیم که فاکتوریل محاسبه میکند:

54321 = 120

شرط پایه برای این تابع عدد 1 است:

function factorial(num){
    if(num === 1){
        return num;
    }

}

console.log(factorial(1));

و بعد نیاز داریم تا تابع خود را صدا بزند. از آنجا که در محاسبه فاکتوریل، در هر مرحله ضرب از عدد یک واحد کم میشود، می توانیم این کار را نوشتن num - 1 شبیه سازی کنیم:

function factorial(num){
    if(num === 1){
        return num;
    }
    return num * factorial(num-1) 
}

console.log(factorial(2));

و تمام. میتوانید تابع را با دادن مقدار 5 به آن امتحان کنید:

console.log(factorial(5));

نتیجه گیری

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

هنگام خواندن تابع بازگشتی باید حالتی که شرط پایه بدون صدا زدن تابع اجرا میشود را پیدا کنید.

وقتی شرط پایه را پیدا کردید، یک پله به عقب برگردید و سعی کنید حداقل یکبار تابع خود را صدا بزند. با این روش، مغز شما تابع بازگشتی و کارکرد آن را به صورت شهودی درک خواهد کرد.

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

منبع