Recursion


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon Infosys MAQ
Recursion Stack ທິດສະດີ

ການເອີ້ນຄືນແມ່ນຫຍັງ?

ການເອີ້ນຄືນແມ່ນຖືກ ກຳ ນົດພຽງແຕ່ວ່າ ໜ້າ ທີ່ເອີ້ນຕົວເອງ. ມັນໃຊ້ບັນດາບັນຫາຍ່ອຍທີ່ຖືກແກ້ໄຂໃນເມື່ອກ່ອນເພື່ອຄິດໄລ່ບັນຫາທີ່ໃຫຍ່ກວ່າ.

ມັນແມ່ນ ໜຶ່ງ ໃນບັນດາແນວຄິດທີ່ ສຳ ຄັນແລະຫຼອກລວງໃນການຂຽນໂປແກຼມແຕ່ພວກເຮົາສາມາດເຂົ້າໃຈໄດ້ງ່າຍຖ້າພວກເຮົາພະຍາຍາມກ່ຽວຂ້ອງກັບການເອີ້ນຄືນດ້ວຍຕົວຢ່າງທີ່ແທ້ຈິງ:

ຍົກຕົວຢ່າງ

ຄິດເຖິງສະຖານະການເມື່ອທ່ານເອົາກະຈົກຢູ່ຕໍ່ ໜ້າ ກະຈົກ?

Recursion

ສິ່ງນີ້ເກີດຂື້ນເພາະວ່າກະຈົກ ກຳ ລັງສະທ້ອນກະຈົກ, ເຊິ່ງ ກຳ ລັງສະທ້ອນກັບກະຈົກ, …ແລະອື່ນໆ.

ນີ້ແມ່ນສິ່ງທີ່ການເອີ້ນຄືນ.

ໃນປັດຈຸບັນໃຫ້ຂອງພະຍາຍາມຈິນຕະນາການວິທີການເຮັດວຽກ recursion:

ຖ້າພວກເຮົາ ກຳ ນົດ ໜ້າ ທີ່ທີ່ຈະແຕ້ມສາມຫຼ່ຽມໃນທຸກຂອບ. ທ່ານສາມາດຈິນຕະນາການຕົວເລກຜົນໄດ້ຮັບບໍ?Recursion

ໃນທັງສອງຕົວຢ່າງຂ້າງເທິງນີ້ພວກເຮົາໄດ້ເຫັນບັນຫາຍ່ອຍທີ່ບໍ່ມີວັນສິ້ນສຸດ (ກະຈົກຈະສືບຕໍ່ສະທ້ອນເຊິ່ງກັນແລະກັນແລະປະກົດວ່າມີ ຈຳ ນວນກະຈົກທີ່ບໍ່ມີຂອບເຂດແລະໃນຕົວຢ່າງທີສອງ, ຕົວເລກຈະສືບຕໍ່ເຕີບໂຕຢ່າງບໍ່ຢຸດຢັ້ງ).

ໂດຍສິ່ງນີ້, ພວກເຮົາເຂົ້າໃຈເຖິງຄວາມ ຈຳ ເປັນຂອງການມີເງື່ອນໄຂສຸດທ້າຍ ສຳ ລັບທຸກໆ ໜ້າ ທີ່ການເອີ້ນຄືນເຊິ່ງຈະຫລີກລ້ຽງໂຄງສ້າງທີ່ບໍ່ມີຂອບເຂດນີ້. ສະພາບການນີ້ແມ່ນເປັນທີ່ຮູ້ຈັກເປັນ ກໍລະນີຖານ.

ຂັ້ນຕອນໃນການສ້າງການຊ້ອມຄືນ

  1. ກໍລະນີຖານ
  2. ການໂທຫາບັນຫາທີ່ນ້ອຍກວ່າ
  3. ການຄິດໄລ່ບັນຫາທີ່ໃຫຍ່ກວ່າໂດຍໃຊ້ບັນຫາຍ່ອຍທີ່ແກ້ໄຂແລ້ວ

ໃຫ້ພະຍາຍາມເຂົ້າໃຈມັນດ້ວຍຕົວຢ່າງ:

ຄຳ ຖາມ: ຄຳ ນວນຜົນບວກຂອງ ຈຳ ນວນ ທຳ ມະຊາດຕໍ່ເນື່ອງເລີ່ມຕົ້ນດ້ວຍ 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

    }

}

Recursion ແລະ Stack

ເມື່ອເປັນ ຫນ້າທີ່ ເອີ້ນວ່າ, ມັນຄອບຄອງຄວາມຊົງ ຈຳ ໃນ stack ເພື່ອເກັບລາຍລະອຽດກ່ຽວກັບການປະຕິບັດ ໜ້າ ທີ່. ແລະໃນເວລາທີ່ຫນ້າທີ່ສິ້ນສຸດລົງ, ຄວາມຊົງຈໍາທີ່ຖືກຄອບຄອງໂດຍມັນກໍ່ຖືກປ່ອຍອອກມາ. ໃນປັດຈຸບັນໃນການເອີ້ນຄືນ, ດັ່ງທີ່ພວກເຮົາຮູ້ວ່າຫນ້າທີ່ຖືກເອີ້ນໃນຕົວມັນເອງ. ເພາະສະນັ້ນໃນທຸກໆການເອີ້ນການເຮັດວຽກ, ບລັອກຂອງ ໜ່ວຍ ຄວາມ ຈຳ ຖືກສ້າງຂື້ນໃນຂັ້ນໄດເພື່ອຖືຂໍ້ມູນຂອງ ໜ້າ ທີ່ປະຕິບັດໃນປະຈຸບັນ. ເມື່ອຟັງຊັນມັນສິ້ນສຸດລົງ, ມັນຈະກັບມາຫາ ຄຳ ທີ່ມັນຖືກຮຽກຮ້ອງໃຫ້ຂຽນເປັນລາຍລັກອັກສອນໃນຟັງຊັນນອກຄືວ່າ, ຟັງຊັນນອກແມ່ນເລີ່ມຈາກບ່ອນທີ່ມັນຢຸດ. ຂໍໃຫ້ເບິ່ງໂຄງສ້າງຄວາມຊົງ ຈຳ ໃນຕົວຢ່າງຂ້າງເທິງນີ້ ສຳ ລັບ n = 3:

ການຮັກສາສະມາຄົມຂອງການຮຽກຮ້ອງແລະການຄິດໄລ່ຄືນ ໃໝ່ ໃນໃຈ, ພວກເຮົາສາມາດເຂົ້າໃຈໄດ້ງ່າຍວ່າໃນກໍລະນີທີ່ບໍ່ມີ Base Case, ໂປຣແກຣມຂອງພວກເຮົາຈະປະສົບກັບຄວາມຫຍຸ້ງຍາກຂອງ Stack ເກີນ ກຳ ນົດແລະເວລາເກີນ ກຳ ນົດ.

ຄວາມແຕກຕ່າງລະຫວ່າງການຄົ້ນຄ້ວາທາງກົງແລະທາງອ້ອມ

ການກວດຄືນໂດຍກົງ

  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
    }
}

ໃນເວລາທີ່ການນໍາໃຊ້ recursion ໃນໄລຍະ iteration

ວິທີການທັງສອງມີຂໍ້ດີແລະຂໍ້ເສຍປຽບຂອງຕົນເອງ, ເພາະສະນັ້ນມັນຈຶ່ງ ຈຳ ເປັນທີ່ຈະຕ້ອງເຂົ້າໃຈວ່າຄວນ ນຳ ໃຊ້ວິທີໃດເພື່ອແກ້ໄຂບັນຫາໃດ ໜຶ່ງ.

Recursive ແມ່ນວິທີການທີ່ມີຄວາມລະອຽດອ່ອນ ສຳ ລັບການແກ້ໄຂບັນຫາ ແບ່ງແລະເອົາຊະນະ ເຊັ່ນການປະສົມປະສານກັນຍ້ອນວ່າພວກເຮົາສາມາດສືບຕໍ່ແບ່ງປັນບັນຫາເຂົ້າໄປໃນບັນຫາຍ່ອຍຂອງມັນຄືນ ໃໝ່ ເຊິ່ງບາງຄັ້ງມັນຍາກທີ່ຈະເຮັດໂດຍໃຊ້ວິທີການຊ້ ຳ ຊ້ອນເຊັ່ນ traversal ຕົ້ນໄມ້(ລາຍການສັ່ງຊື້, ສັ່ງຊື້, ສັ່ງກ່ອນ). ແຕ່ວ່າມັນຍັງເປັນຄວາມຈິງທີ່ວ່າວິທີການປ່ຽນແປງແມ່ນໄວກ່ວາການຮຽກຮ້ອງຄືນ ໃໝ່ ຍ້ອນວ່າບໍ່ມີການສິ້ນສຸດການໂທຫຼາຍ ໜ້າ ທີ່.

ໝາຍ ເຫດ: ເພື່ອແກ້ໄຂບັນຫາໃດ ໜຶ່ງ ພວກເຮົາສາມາດໃຊ້ ຄຳ ເວົ້າຫລືການເອີ້ນຄືນຫລືທັງສອງຢ່າງ.

ການເອີ້ນຄືນສາມາດຖືກທົດແທນດ້ວຍ iteration ດ້ວຍ stack call ທີ່ຊັດເຈນ, ໃນຂະນະທີ່ iteration ສາມາດຖືກທົດແທນດ້ວຍ 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

ການປະຕິບັດ Java

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

ຂອບໃຈທີ່ອ່ານ !!

ຕິດຕາມແລະກວດເບິ່ງບລັອກອື່ນໆອີກ. ຄໍາເຫັນລົງສໍາລັບການແກ້ໄຂ / ຄໍາແນະນໍາໃດໆ.

ເອກະສານ