ዳግም መጥፋት


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ኢንፎሲስ MAQ
ዳግም መጥፋት ክምር ፍልስፍና

መዝናኛ ምንድን ነው?

መመለሻ በቀላሉ እራሱን እንደ ሚጠራው ተግባር ይገለጻል ፡፡ ትልቁን ችግር ለማስላት ከዚህ በፊት የተፈቱትን ንዑስ ችግሮች ይጠቀማል ፡፡

እሱ በፕሮግራም ውስጥ በጣም አስፈላጊ እና ተንኮለኛ ከሆኑ ፅንሰ-ሀሳቦች አንዱ ነው ነገር ግን ከአንዳንድ እውነተኛ ምሳሌዎች ጋር መመለሻን ለማያያዝ ከሞከርን በቀላሉ ልንረዳው እንችላለን

ለምሳሌ

መስታወት ከመስታወት ፊት ለፊት ሲያስቀምጡ ስለ አንድ ሁኔታ ያስቡ?

ዳግም መጥፋት

ይህ የሚሆነው አንድ መስታወት መስታወት የሚያንፀባርቅ ነው ፣ እሱም መስታወት የሚያንፀባርቅ ነው ፣… እና የመሳሰሉት።

ይህ ሪዞረንስ የሚያደርገው በትክክል ነው ፡፡

አሁን እንደገና መመለስ እንዴት እንደሚሰራ በዓይነ ሕሊናችን ለመመልከት እንሞክር-

በእያንዳንዱ ጠርዝ ላይ ሶስት ማእዘን ለመሳል አንድ ተግባር ከገለጽን ፡፡ የውጤቱን ቁጥር መገመት ይችላሉ?ዳግም መጥፋት

ከላይ በተጠቀሱት ሁለቱም ምሳሌዎች ማለቂያ የሌላቸውን ንዑስ ችግሮች ተመልክተናል (መስታወቶቹ እርስ በርሳቸው የሚያንፀባርቁ መሆናቸው የማይቀር የመስታወት ብዛት ያለ ይመስላል እና በሁለተኛው ምሳሌ ደግሞ ቁጥሩ ያለገደብ እያደገ ይሄዳል) ፡፡

በዚህ ፣ ይህንን ማለቂያ የሌለው መዋቅርን የሚያስወግድ ለእያንዳንዱ ተደጋጋሚ ተግባር የመጨረሻ ሁኔታ የማግኘት አስፈላጊነት እንገነዘባለን ፡፡ ይህ ሁኔታ በመባል ይታወቃል የመሠረት ጉዳይ.

ሪዞርስን ለመፍጠር ደረጃዎች

  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:

የጉብኝት እና የቁጥር ማህበርን በአእምሯችን በመያዝ ፣ ቤዝ ኬዝ ከሌለ ፕሮግራማችን በስታክ ፍሰት ከመጠን በላይ እንደሚሰቃይ እና የጊዜ ገደቡ እንደሚጨምር በቀላሉ መረዳት እንችላለን ፡፡

ቀጥተኛ እና ቀጥተኛ ያልሆነ ምልመላ ልዩነት

ቀጥተኛ መመለሻ

  1. ተመሳሳይ ተግባር ራሱን ሲጠራ ከዚያ እንደሚታወቅ ይታወቃል ቀጥተኛ መመለሻ.
  2. በቀጥታ ምልመላ ውስጥ ሁለቱም መደወልም ሆነ መጥራት ተግባር አንድ ነው ፡፡
  3. የአንድ-ደረጃ ተደጋጋሚ ጥሪ ይኖራል ፡፡

የቀጥታ ተደጋጋሚ ተግባር የኮድ መዋቅር

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

  func_name(parameters);

  // some code...
}

ቀጥተኛ ያልሆነ ምልመላ

  1. አንድ ተግባር በቀጥታም ሆነ በተዘዋዋሪ የወላጆችን ተግባር የሚጠራውን ሌላ ተግባር ሲጠራ ከዚያ ይታወቃል ቀጥተኛ ያልሆነ ምልመላ
  2. በተዘዋዋሪ Recursion ውስጥ መደወል እና መደወል ተግባራት የተለያዩ ናቸው ፡፡
  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
    }
}

በመድገም ላይ እንደገና መመለሻን መቼ እንደሚጠቀሙ

ሁለቱም አቀራረቦች የራሳቸው ጥቅሞች እና ጉዳቶች አሏቸው ፣ ስለሆነም አንድን የተወሰነ ችግር ለመፍታት የትኛው ጥቅም ላይ መዋል እንዳለበት መረዳቱ አስፈላጊ ይሆናል ፡፡

ችግሮችን ለመፍታት የበለጠ ተደጋጋሚ (recursive) ነው መከፋፈል እና ማሸነፍ እንደ ማዋሃድ ዓይነት ችግሩን በተደጋጋሚ ወደ ንዑስ ችግሮ breaking መከፋፈሉን መቀጠል እንደምንችል እና አንዳንድ ጊዜ ተደጋጋሚ አካሄድን በመጠቀም ለማከናወን አስቸጋሪ ነው ፣ ለምሳሌ ፣ የዛፍ መተላለፍ(Inorder, Preorder, Postorder). ግን ደግሞ የብዙ ተግባር ጥሪዎች አናት ስላልተገኙ የመለዋወጥ ዘዴው ከመመለስ የበለጠ ፈጣን ነው ፡፡

ማስታወሻ-አንድን ችግር ለመፍታት መደጋገም ወይም መደጋገም ወይንም ሁለቱንም ቢሆን መጠቀም እንችላለን ፡፡

ድግግሞሽ በግልፅ የጥሪ ቁልል በመድገም ሊተካ ይችላል ፣ ግን ድግግሞሽ በጅራት_ሬክursርዮን ሊተካ ይችላል። እኛ እንደ ፕሮግራመር በቀላል እና በንጹህ የኮድ አፃፃፍ መካከል በማስታወስ እና በጊዜ ማመቻቸት መካከል ሚዛንን መፍጠር አለብን ፡፡

ሌላ ጥያቄ ለመፍታት እንሞክር-

የ 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

በማንበብ እናመሰግናለን !!

ይቆዩ እና ሌሎች ብሎጎችንም ይፈትሹ ፡፡ ለማንኛውም እርማቶች / ጥቆማዎች አስተያየት ይስጡ ፡፡

ማጣቀሻዎች