રિકર્ઝન


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન ઇન્ફોસિસ MAQ
રિકર્ઝન સ્ટેક થિયરી

રિકર્ઝન એટલે શું?

રિકર્ઝન એ ફક્ત પોતાને બોલાવવાનું કાર્ય તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. મોટી સમસ્યાનું ગણતરી કરવા માટે તે તેની પહેલા હલ થયેલ પેટા-સમસ્યાઓનો ઉપયોગ કરે છે.

તે પ્રોગ્રામિંગની સૌથી મહત્વપૂર્ણ અને મુશ્કેલ ખ્યાલો છે પરંતુ જો આપણે કેટલાક વાસ્તવિક ઉદાહરણો સાથે રિકર્ઝનને જોડવાનો પ્રયત્ન કરીએ તો આપણે તેને સરળતાથી સમજી શકીએ છીએ:

ઉદાહરણ

જ્યારે તમે અરીસાની સામે અરીસો મુકો છો ત્યારે પરિસ્થિતિનો વિચાર કરો?

રિકર્ઝન

આવું થાય છે કારણ કે એક અરીસો અરીસાને પ્રતિબિંબિત કરે છે, જે દર્પણને પ્રતિબિંબિત કરે છે… અને તેથી વધુ.

આ બરાબર તે જ છે જે રિકર્ઝન કરે છે.

હવે ચાલો રિકર્ઝન કેવી રીતે કાર્ય કરે છે તે કલ્પના કરવાનો પ્રયાસ કરીએ:

જો આપણે ફંક્શનને તેના દરેક ધાર પર ત્રિકોણ દોરવા માટે વ્યાખ્યાયિત કરીએ છીએ. શું તમે પરિણામી આકૃતિની કલ્પના કરી શકો છો?રિકર્ઝન

ઉપરોક્ત બંને ઉદાહરણોમાં આપણે ક્યારેય ન સમાયેલી પેટા-સમસ્યાઓ જોઇ છે (અરીસાઓ એક બીજાને પ્રતિબિંબિત કરતા રહેશે અને ત્યાં અરીસોની અસંખ્ય સંખ્યા દેખાય છે અને બીજા ઉદાહરણમાં, આંકડો અનંત વધતો રહેશે).

આ દ્વારા, અમે દરેક પુનરાવર્તિત કાર્યો માટે અંત સ્થિતિની જરૂરિયાત સમજીએ છીએ જે આ અનંત રચનાને ટાળશે. આ સ્થિતિ તરીકે ઓળખાય છે આધાર કેસ.

રિકર્ઝન રચવાના પગલાં

  1. આધાર કેસ
  2. નાની સમસ્યા માટે રિકરિવ ક callલ
  3. હલ પેટા-સમસ્યાઓનો ઉપયોગ કરીને મોટી સમસ્યાની ગણતરી

ચાલો તેને ઉદાહરણ સાથે સમજવાનો પ્રયત્ન કરીએ:

Ques: 1 થી શરૂ થતાં સતત n કુદરતી સંખ્યાના સરવાળાની ગણતરી કરો.

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

    }

}

પુનરાવર્તન અને સ્ટેક

જ્યારે એક કાર્ય કહેવામાં આવે છે, તે મેમરીમાં કબજો કરે છે સ્ટેક ફંકશનના અમલ વિશેની વિગતો સંગ્રહિત કરવા. અને જ્યારે ફંકશન સમાપ્ત થાય છે, ત્યારે તેની દ્વારા કબજે કરેલી મેમરી પણ પ્રકાશિત થાય છે. હવે રિકર્ઝનમાં, આપણે જાણીએ છીએ કે એક ફંકશન પોતે કહેવામાં આવે છે. તેથી, દરેક ફંક્શન ક callલ પર, હાલમાં એક્ઝેક્યુટ કરેલા ફંક્શનની માહિતીને રાખવા સ્ટેકમાં મેમરીનો બ્લોક બનાવવામાં આવે છે. જ્યારે ફંકશન સમાપ્ત થાય છે, ત્યારે તે બાહ્ય ફંક્શનમાં લખેલા ક callingલિંગ સ્ટેટમેન્ટ પર પાછું આવે છે, જેમ કે બાહ્ય કાર્ય જ્યાંથી અટક્યું ત્યાંથી ફરી શરૂ થાય છે. ચાલો n = 3 માટે ઉપરના ઉદાહરણમાં મેમરી સ્ટ્રક્ચર જોઈએ.

પુનરાવર્તન અને સ્ટેકને ધ્યાનમાં રાખીને, અમે સરળતાથી સમજી શકીએ છીએ કે બેઝ કેસની ગેરહાજરીમાં, અમારું પ્રોગ્રામ સ્ટેક ઓવરફ્લો સાથે સહન કરશે અને સમય મર્યાદા ઓળંગી ગઈ.

પ્રત્યક્ષ અને પરોક્ષ પુનરાવર્તન વચ્ચેનો તફાવત

ડાયરેક્ટ રિકર્ઝન

  1. જ્યારે તે જ ફંક્શન પોતે બોલાવે છે ત્યારે તે તરીકે ઓળખાય છે ડાયરેક્ટ રિકર્ઝન.
  2. ડાયરેક્ટ રિકર્ઝનમાં, ક callingલિંગ અને ક calledલ કરેલું બંને કાર્ય સમાન છે.
  3. એક-પગલું રિકર્સીવ ક callલ આવશે.

ડાયરેક્ટ રિકર્સીવ ફંક્શનની કોડ સ્ટ્રક્ચર:

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

  func_name(parameters);

  // some code...
}

પરોક્ષ રિકર્ઝન

  1. જ્યારે કોઈ ફંક્શન કોઈ અન્ય ફંક્શનને બોલાવે છે જે તેના પેરેંટ ફંક્શનને સીધા અથવા પરોક્ષ રીતે બોલાવે છે, તો તે તરીકે ઓળખાય છે પરોક્ષ રિકર્ઝન.
  2. પરોક્ષ રિકર્ઝનમાં, ક callingલિંગ અને ક functionsલ કરેલા કાર્યો અલગ છે.
  3. મલ્ટિ-સ્ટેપ રીકર્સિવ ક callલ આવશે.

પરોક્ષ રિકર્સીવ ફંક્શનની કોડ સ્ટ્રક્ચર:

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. ટાઇલ્ડ રિકર્ઝન
    • જ્યારે ફંકશનનું છેલ્લું એક્ઝેક્યુટ કરેલું નિવેદન પુનરાવર્તિત ક callલ છે.
    • સ્ટેક પર ફક્ત છેલ્લા રિકરિવ ક callલ રાખવાનું શક્ય છે.
    • ઉદાહરણ:
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. બિન-પૂંછડી રિકર્ઝન
    • જ્યારે ફર્કસમાં રિકરિવ કોલ સ્ટેટમેંટ પછી એક્ઝેક્યુટ કરવા માટેનાં સ્ટેટમેન્ટ બાકી છે.
    • પુનરાવર્તિત ક callલ તેના મૂલ્યાંકનના અંત સુધી સ્ટેકમાં રહેશે.
    • ઉદાહરણ:
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
    }
}

જ્યારે પુનરાવર્તન ઉપર પુનરાવર્તનનો ઉપયોગ કરવો

બંને અભિગમોના પોતાના ગુણ અને વિપક્ષ છે, તેથી તે સમજવું જરૂરી બને છે કે કોઈ ખાસ સમસ્યા હલ કરવા માટે કયો ઉપયોગ કરવો જોઈએ.

ની સમસ્યાઓ હલ કરવા માટે રિકરિવ એ વધુ સાહજિક અભિગમ છે ભાગો અને જીતવા મર્જ સ sortર્ટ જેવા કે આપણે સમસ્યાને તેની પેટા-સમસ્યાઓમાં વારંવાર તોડતા રાખી શકીએ છીએ જે કેટલીક વાર પુનરાવર્તિત અભિગમનો ઉપયોગ કરીને કરવાનું મુશ્કેલ છે, ઉદાહરણ તરીકે, વૃક્ષની આડઅસર(ઇનઓર્ડર, પ્રિઓર્ડર, પોસ્ટ Postર્ડર). પરંતુ તે પણ સાચું છે કે મલ્ટિપલ ફંક્શન કોલ્સનો કોઈ ઓવરહેડ ન હોવાને કારણે પુનરાવર્તિત અભિગમ પુનરાવર્તન કરતા ઝડપી છે.

નોંધ: કોઈ સમસ્યા હલ કરવા માટે આપણે ઇટરેશન અથવા રિકર્ઝન અથવા તો બંને વાપરી શકીએ છીએ.

રિકર્ઝન ઇટરેશન દ્વારા સ્પષ્ટ કોલ સ્ટેક સાથે બદલી શકાય છે, જ્યારે ઇટરેશનને પૂંછડી_પ્રાપ્તિ સાથે બદલી શકાય છે. આપણે પ્રોગ્રામર તરીકે મેમરી અને સમય optimપ્ટિમાઇઝેશન સાથે કોડના સરળ અને સ્વચ્છ લેખન વચ્ચે સંતુલન બનાવવું જોઈએ.

ચાલો બીજો પ્રશ્ન હલ કરવાનો પ્રયાસ કરીએ:

એન ની ફેકટોરીયલ ગણતરી.

સી ++ અમલીકરણ

#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

વાંચવા માટે આભાર !!

ચાલુ રહો અને અન્ય બ્લોગ્સ પણ તપાસો. કોઈપણ સુધારા / સૂચનો માટે ટિપ્પણી કરો.

સંદર્ભ