باز گشت


سطح دشواری ساده
اغلب در آمازون Infosys در MAQ
باز گشت پشته نظریه

بازگشت چیست؟

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

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

مثال

به حالتی فکر می کنید که آینه را جلوی آینه قرار دهید؟

باز گشت

این اتفاق می افتد زیرا آینه منعکس کننده آینه است ، که منعکس کننده یک آینه است ، ... و غیره.

این دقیقاً همان کاری است که بازگشت انجام می دهد.

حال بیایید سعی کنیم نحوه بازگشت را تجسم کنیم:

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

در هر دو مثال فوق ، مشکلات فرعی پایان ناپذیری را مشاهده کردیم (آینه ها بازتاب دهنده یکدیگر خواهند بود و به نظر می رسد تعداد بی نهایت آینه وجود دارد و در مثال دوم ، این شکل به رشد بی نهایت ادامه خواهد داد).

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

مراحل تشکیل بازگشت

  1. مورد پایه
  2. تماس برگشتی برای مشکل کوچکتر
  3. محاسبه مسئله بزرگتر با استفاده از زیرمشکلات حل شده

بیایید سعی کنیم آن را با یک مثال درک کنیم:

س Quesال: جمع n عدد طبیعی متوالی را با شروع با 1 محاسبه کنید.

int sum(int n){

    // Base Case

    if(n==1){

        return n;

    }

    else{

        int smallerSum=sum(n-1);      //recursive call for smaller problem

        return n+smallerSum;         // solve bigger problem using solved smaller sub-problems

    }

}

بازگشت و پشته

هنگامی که یک تابع نامیده می شود ، حافظه را در پشته برای ذخیره جزئیات مربوط به اجرای عملکرد. و هنگامی که عملکرد به پایان می رسد ، حافظه اشغال شده توسط آن نیز آزاد می شود. اکنون در بازگشت ، همانطور که می دانیم تابعی به خودی خود فراخوانی می شود. از این رو در هر تماس تابع ، یک بلوک حافظه در پشته ایجاد می شود تا اطلاعات عملکرد فعلی در حال اجرا را داشته باشد. وقتی این تابع پایان می یابد ، به عبارت فراخوانی نوشته شده در تابع بیرونی برمی گردد ، یعنی یک تابع خارجی از جایی که متوقف شده است از سر گرفته می شود. بیایید ساختار حافظه را در مثال بالا برای n = 3 ببینیم:

با در نظر داشتن ارتباط بازگشت و پشته ، به راحتی می توان فهمید که در صورت عدم وجود Base Case ، برنامه ما با سرریز Stack و بیش از محدودیت زمانی آسیب خواهد دید.

تفاوت بازگشت مستقیم و غیرمستقیم

بازگشت مستقیم

  1. هنگامی که همان عملکرد خود را فراخوانی می کند ، آن را به عنوان شناخته می شود بازگشت مستقیم.
  2. در Direct Recursion ، عملکرد فراخوانی و فراخوانی یکسان است.
  3. یک تماس بازگشتی یک مرحله ای برقرار خواهد شد.

ساختار کد عملکرد بازگشتی مستقیم:

return_type func_name(arguments)
{
  // some code...

  func_name(parameters);

  // some code...
}

بازگشت غیرمستقیم

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

ساختار کد تابع بازگشتی غیرمستقیم:

return_type func_name1(arguments)
{
  // some code...

  func_name2(parameters);

  // some code...
}

return_type func_name2(arguments)
{
  // some code...

  func_name1(parameters);

  // some code...
}

انواع بازگشت

  1. بازگشت دم
    • وقتی آخرین دستور اجرا شده یک عملکرد بازگشتی است.
    • فقط می توان آخرین تماس بازگشتی را روی پشته نگه داشت.
    • مثال:
int sum(int n,int &ans){
    if(n==0){
        return ans;
    }
    else{
        ans=ans+n;
        return sum(n-1,ans);     // last statement to be executed is recursive call

    }
}
  1. بازگشت بدون دم
    • هنگامی که عبارات در عملکرد باقی مانده است تا بعد از دستور بازگشتی اجرا شود.
    • تماس برگشتی تا پایان ارزیابی در پشته باقی خواهد ماند.
    • مثال:
int sum(int n){
    if(n==1){
        return n;
    }
    else{
        int smallerSum=sum(n-1);      //recursive call for smaller problem
        return n+smallerSum;         //statements to be executed after recursive call
    }
}

چه زمانی باید از بازگشت بر روی تکرار استفاده کرد

هر دو رویکرد مزایا و معایب خاص خود را دارند ، از این رو درک این نکته ضروری می شود که برای حل یک مشکل خاص باید از کدام یک استفاده کرد.

بازگشتی یک رویکرد شهودی برای حل مشکلات است تفرقه بینداز و حکومت کن مانند مرتب سازی ادغام زیرا ما می توانیم مسئله را به صورت بازگشتی به زیرمشکلات خود ادامه دهیم ، که انجام آن با استفاده از رویکرد تکرار شونده گاهی دشوار است ، به عنوان مثال ، تراش درخت(Inorder ، Preorder ، Postorder). اما این نیز درست است که رویکرد تکراری سریعتر از بازگشت است زیرا سربار فراخوانی چندین عملکرد وجود ندارد.

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

بازگشت را می توان با تکرار با یک پشته تماس صریح جایگزین کرد ، در حالی که تکرار را می توان با tail_recursion جایگزین کرد. ما به عنوان یک برنامه نویس باید تعادلی بین آسان و تمیز نوشتن کد با حافظه و بهینه سازی زمان ایجاد کنیم.

بیایید سعی کنیم یک سوال دیگر را حل کنیم:

فاکتوریل n را محاسبه کنید.

اجرای C ++

#include <iostream>
using namespace std;
int fact(int n){
   // Base Case
   if (n <= 1)
        return 1;
   else 
       return n*fact(n-1);    
}
int main(){
   int n=5;
   cout<<fact(n);
   return 0;
}
Output: 15

پیاده سازی جاوا

class Main{  
 static int fact(int n){    
  if (n<=1)    
    return 1;    
  else    
    return(n * fact(n-1));    
 }    
 public static void main(String args[]){  
  int n=5;   
  System.out.println(fact(n));    
 }  
}
Output: 15

با تشکر از خواندن !!

با ما همراه باشید و سایر وبلاگ ها را نیز بررسی کنید. برای هرگونه اصلاح / پیشنهاد نظر دهید.

منابع