റിക്കറിഷൻ  


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഇൻഫോസിസ് MAQ
റിക്കറിഷൻ കൂനകൂട്ടുക സിദ്ധാന്തം

എന്താണ് ആവർത്തനം?

ആവർത്തനത്തെ ഒരു ഫംഗ്ഷൻ തന്നെ വിളിക്കുന്നു. ഒരു വലിയ പ്രശ്‌നം കണക്കാക്കാൻ ഇത് മുമ്പ് പരിഹരിച്ച ഉപ പ്രശ്‌നങ്ങൾ ഉപയോഗിക്കുന്നു.

പ്രോഗ്രാമിംഗിലെ ഏറ്റവും പ്രധാനപ്പെട്ടതും തന്ത്രപരവുമായ ആശയങ്ങളിൽ ഒന്നാണിത്, പക്ഷേ ചില യഥാർത്ഥ ഉദാഹരണങ്ങളുമായി ആവർത്തനത്തെ ബന്ധിപ്പിക്കാൻ ശ്രമിച്ചാൽ നമുക്ക് അത് എളുപ്പത്തിൽ മനസ്സിലാക്കാൻ കഴിയും:

ഉദാഹരണം  

നിങ്ങൾ ഒരു കണ്ണാടിക്ക് മുന്നിൽ ഒരു കണ്ണാടി ഇടുമ്പോൾ ഒരു സാഹചര്യത്തെക്കുറിച്ച് ചിന്തിക്കുക?

റിക്കറിഷൻമൊട്ടുസൂചി

ഇത് സംഭവിക്കുന്നത് ഒരു കണ്ണാടി ഒരു കണ്ണാടിയെ പ്രതിഫലിപ്പിക്കുന്നതിനാലാണ്, അത് ഒരു കണ്ണാടി പ്രതിഫലിപ്പിക്കുന്നു,… അങ്ങനെ.

ആവർത്തനമാണ് ഇത് ചെയ്യുന്നത്.

ആവർത്തനം എങ്ങനെ പ്രവർത്തിക്കുന്നുവെന്ന് ദൃശ്യവൽക്കരിക്കാൻ ശ്രമിക്കാം:

ഒരു ത്രികോണം അതിന്റെ ഓരോ അരികിലും വരയ്ക്കുന്നതിന് ഞങ്ങൾ ഒരു ഫംഗ്ഷൻ നിർവചിക്കുകയാണെങ്കിൽ. ഫലമായുണ്ടാകുന്ന കണക്ക് നിങ്ങൾക്ക് imagine ഹിക്കാമോ?റിക്കറിഷൻമൊട്ടുസൂചി

മേൽപ്പറഞ്ഞ രണ്ട് ഉദാഹരണങ്ങളിലും ഒരിക്കലും അവസാനിക്കാത്ത ഉപപ്രശ്നങ്ങൾ ഞങ്ങൾ കണ്ടു (കണ്ണാടികൾ പരസ്പരം പ്രതിഫലിപ്പിച്ചുകൊണ്ടിരിക്കും, കൂടാതെ അനന്തമായ കണ്ണാടികൾ ഉണ്ടെന്ന് തോന്നുന്നു, രണ്ടാമത്തെ ഉദാഹരണത്തിൽ, ഈ കണക്ക് അനന്തമായി വർദ്ധിച്ചുകൊണ്ടിരിക്കും).

ഈ അനന്തമായ ഘടനയെ ഒഴിവാക്കുന്ന ഓരോ ആവർത്തന പ്രവർത്തനത്തിനും ഒരു അന്തിമ അവസ്ഥ ഉണ്ടായിരിക്കേണ്ടതിന്റെ ആവശ്യകത ഞങ്ങൾ മനസ്സിലാക്കുന്നു. ഈ അവസ്ഥയെ അറിയപ്പെടുന്നു അടിസ്ഥാന കേസ്.

ആവർത്തന രൂപീകരണത്തിനുള്ള ഘട്ടങ്ങൾ  

  1. അടിസ്ഥാന കേസ്
  2. ചെറിയ പ്രശ്‌നത്തിനായുള്ള ആവർത്തന കോൾ
  3. പരിഹരിച്ച ഉപ പ്രശ്‌നങ്ങൾ ഉപയോഗിച്ച് വലിയ പ്രശ്‌നത്തിന്റെ കണക്കുകൂട്ടൽ

ഒരു ഉദാഹരണം ഉപയോഗിച്ച് ഇത് മനസിലാക്കാൻ ശ്രമിക്കാം:

ക്യൂസ്: 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

    }

}

ആവർത്തനവും സ്റ്റാക്കും  

എപ്പോഴാണ് ഒരു ഫംഗ്ഷൻ എന്ന് വിളിക്കുന്നു, ഇത് മെമ്മറി ഉൾക്കൊള്ളുന്നു സ്റ്റാക്ക് ഫംഗ്ഷന്റെ എക്സിക്യൂഷനെക്കുറിച്ചുള്ള വിശദാംശങ്ങൾ സംഭരിക്കുന്നതിന്. ഫംഗ്ഷൻ അവസാനിക്കുമ്പോൾ, അതിൽ അടങ്ങിയിരിക്കുന്ന മെമ്മറിയും പുറത്തുവിടുന്നു. ഇപ്പോൾ ആവർത്തനത്തിലാണ്, നമുക്കറിയാവുന്നതുപോലെ ഒരു ഫംഗ്ഷൻ തന്നെ വിളിക്കുന്നു. അതിനാൽ ഓരോ ഫംഗ്ഷൻ കോളിലും, നിലവിൽ എക്സിക്യൂട്ട് ചെയ്യുന്ന ഫംഗ്ഷന്റെ വിവരങ്ങൾ സൂക്ഷിക്കുന്നതിന് സ്റ്റാക്കിൽ ഒരു ബ്ലോക്ക് മെമ്മറി സൃഷ്ടിക്കപ്പെടുന്നു. ഫംഗ്ഷൻ അവസാനിക്കുമ്പോൾ, അത് ബാഹ്യ ഫംഗ്ഷനിൽ എഴുതിയ കോളിംഗ് സ്റ്റേറ്റ്മെന്റിലേക്ക് മടങ്ങുന്നു, അതായത്, ഒരു ബാഹ്യ ഫംഗ്ഷൻ നിർത്തിയ സ്ഥലത്ത് നിന്ന് പുനരാരംഭിക്കുന്നു. മുകളിലുള്ള ഉദാഹരണത്തിൽ n = 3 എന്നതിനായി മെമ്മറി ഘടന നോക്കാം:

ഇതും കാണുക
കൂൾ‌ഡ own ൺ‌ ലീറ്റ്‌കോഡ് സൊല്യൂഷൻ ഉപയോഗിച്ച് സ്റ്റോക്ക് വാങ്ങാനും വിൽക്കാനുമുള്ള മികച്ച സമയം

മൊട്ടുസൂചി

ആവർത്തനത്തിന്റെയും സ്റ്റാക്കിന്റെയും ബന്ധം മനസ്സിൽ വച്ചുകൊണ്ട്, അടിസ്ഥാന കേസിന്റെ അഭാവത്തിൽ, സ്റ്റാക്ക് ഓവർഫ്ലോയും സമയപരിധിയും കവിഞ്ഞതിനാൽ ഞങ്ങളുടെ പ്രോഗ്രാം ബാധിക്കുമെന്ന് ഞങ്ങൾക്ക് എളുപ്പത്തിൽ മനസ്സിലാക്കാൻ കഴിയും.

നേരിട്ടുള്ള, പരോക്ഷ ആവർത്തനം തമ്മിലുള്ള വ്യത്യാസം  

നേരിട്ടുള്ള ആവർത്തനം

  1. ഒരേ ഫംഗ്ഷൻ സ്വയം വിളിക്കുമ്പോൾ അതിനെ അറിയപ്പെടുന്നു നേരിട്ടുള്ള ആവർത്തനം.
  2. നേരിട്ടുള്ള ആവർത്തനത്തിൽ, കോളിംഗും വിളിക്കുന്ന പ്രവർത്തനവും ഒന്നുതന്നെയാണ്.
  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). ഒന്നിലധികം ഫംഗ്ഷൻ കോളുകളുടെ ഓവർഹെഡ് ഇല്ലാത്തതിനാൽ ആവർത്തന സമീപനം ആവർത്തനത്തേക്കാൾ വേഗതയുള്ളതാണെന്നതും ശരിയാണ്.

കുറിപ്പ്: ഒരു പ്രശ്നം പരിഹരിക്കാൻ നമുക്ക് ആവർത്തനം അല്ലെങ്കിൽ ആവർത്തനം അല്ലെങ്കിൽ രണ്ടും ഉപയോഗിക്കാം.

ആവർത്തനത്തെ സ്പഷ്ടമായ കോൾ സ്റ്റാക്ക് ഉപയോഗിച്ച് ആവർത്തനത്തെ മാറ്റിസ്ഥാപിക്കാം, അതേസമയം ആവർത്തനത്തെ ടെയിൽ_റികർഷൻ ഉപയോഗിച്ച് മാറ്റിസ്ഥാപിക്കാം. ഒരു പ്രോഗ്രാമർ എന്ന നിലയിൽ മെമ്മറിയും സമയ ഒപ്റ്റിമൈസേഷനും ഉപയോഗിച്ച് എളുപ്പത്തിലും വൃത്തിയായും കോഡ് എഴുതുന്നത് തമ്മിൽ ഒരു ബാലൻസ് സൃഷ്ടിക്കണം.

മറ്റൊരു ചോദ്യം പരിഹരിക്കാൻ ശ്രമിക്കാം:

N ന്റെ ഫാക്റ്റോറിയൽ കണക്കാക്കുക.

സി ++ നടപ്പിലാക്കൽ

#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

വായിച്ചതിന് നന്ദി !!

തുടരുക, മറ്റ് ബ്ലോഗുകളും പരിശോധിക്കുക. ഏതെങ്കിലും തിരുത്തലുകൾ / നിർദ്ദേശങ്ങൾക്കായി അഭിപ്രായമിടുക.

അവലംബം