רקורסיה


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית אינפוסיס מאק
רקורסיה לערום תֵאוֹרִיָה

מה זה רקורסיה?

רקורסיה מוגדרת בפשטות כפונקציה הקוראת לעצמה. היא משתמשת בבעיות המשנה שנפתרו בעבר כדי לחשב בעיה גדולה יותר.

זהו אחד המושגים החשובים והמסובכים בתכנות, אך אנו יכולים להבין זאת בקלות אם ננסה להתייחס לרקורסיה עם כמה דוגמאות אמיתיות:

דוגמה

תחשוב על מצב שבו אתה שם מראה מול מראה?

רקורסיה

זה קורה משום שמראה משקפת מראה, המשקפת מראה, וכן הלאה.

זה בדיוק מה שעושה רקורסיה.

בואו ננסה לדמיין כיצד פועל רקורסיה:

אם נגדיר פונקציה לשרטוט משולש על כל קצה שלו. האם אתה יכול לדמיין את הדמות שהתקבלה?רקורסיה

בשתי הדוגמאות הנ"ל ראינו את בעיות המשנה הבלתי נגמרות (המראות ישקפו כל הזמן ונראה שיש אינסוף מראות ובדוגמה השנייה, הדמות תמשיך לגדול לאינסוף).

על ידי זה אנו מבינים את הצורך בתנאי קצה לכל פונקציה רקורסיבית אשר תמנע מבנה אינסופי זה. מצב זה מכונה מקרה יסוד.

צעדים לגיבוש רקורסיה

  1. מקרה יסוד
  2. שיחה רקורסיבית לבעיה הקטנה יותר
  3. חישוב של בעיה גדולה יותר באמצעות בעיות תת פתורות

בואו ננסה להבין את זה בדוגמה:

שורות: חישב את סכום 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. ב- 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
    }
}

מתי להשתמש ברקורסיה על פני איטרציה

לשתי הגישות יתרונות וחסרונות משלהם, ולכן יש צורך להבין באיזו מהן יש להשתמש כדי לפתור בעיה מסוימת.

רקורסיבית היא גישה אינטואיטיבית יותר לפתרון בעיות של הפרד ומשול כמו למיזוג מיון מכיוון שנוכל להמשיך ולפרוץ את הבעיה לבעיות המשנה שלה באופן רקורסיבי, שלעתים קשה לעשות זאת באמצעות גישה איטרטיבית, למשל, מעבר עצים(הזמנה, הזמנה מראש, הזמנה חוזרת). אך נכון גם כי הגישה האיטרטיבית מהירה יותר מאשר רקורסיה מכיוון שאין תקורה של שיחות פונקציה מרובות.

הערה: כדי לפתור בעיה נוכל להשתמש באיטרציה או רקורסיה או אפילו בשניהם.

ניתן להחליף את הרקורסיה באמצעות איטרציה עם ערימת קריאה מפורשת, ואילו את האיטרציה ניתן להחליף ב- 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

תודה שקראתם !!

הישאר מעודכן ובדוק גם את הבלוגים האחרים. הגב למטה לתיקונים / הצעות.

הפניות