במילים פשוטות, רקורסיה היא דרך לפתור את הבעיה על ידי קריאת פונקציה עצמה, המילה ' רקורסיבי 'מקורו בפועל הלטיני' לְהִתְרַחֵשׁ שֵׁנִית ”, שפירושו לבצע מחדש משהו. זה מה שהפונקציה הרקורסיבית עושה, היא עושה את אותו הדבר שוב ושוב, כלומר היא נזכרת בעצמה. במאמר זה נלמד על רקורסיה בפיתון. להלן הנושאים הניתנים בבלוג זה:
- מהי רקורסיה בפייתון?
- תנאי סיום
- מגבלת הרקורסיה של פייתון
- רישום רשימות עם רקורסיה
- יתרונות הרקורסיה
- חסרונות של רקורסיה
מהי רקורסיה בפייתון?
רקורסיה היא תהליך של קביעת משהו מבחינת עצמו. אנו יודעים שבפייתון כל פונקציה יכולה לקרוא לכל פונקציה אחרת, פונקציה יכולה גם לקרוא לעצמה. פונקציות מסוג זה המכנות את עצמן עד שלא מתקיים התנאי המסוים מכונות כפונקציות רקורסיביות.
בוא ניקח כמה דוגמאות כדי לראות איך זה עובד, אם יינתן לך מספר שלם חיובי n המפעל יהיה.
שיעור סורק בדוגמה של Java
- n! = n * (n-1) * (n-2) וכן הלאה.
- 2! = 2 * (2-1)
- אחד! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
החלפת הערכים לעיל תביא לביטוי הבא
- 4! = 4 * 3 * 2 * 1
עלינו להגדיר פונקציה נניח עובדה (n) שלוקחת את המספר השלם החיובי או 0 כפרמטר שלה ומחזירה את הפקטוריון ה- n, כיצד נוכל לעשות זאת באמצעות רקורסיה?
בואו נראה, כדי לעשות זאת באמצעות רקורסיה עלינו לבחון את המשוואה הבאה
n! = n. (n-1). (n-2) & hellip3.2.1
n! = n. (n-1)! # אנו יכולים לשכתב את ההצהרה לעיל כמו בשורה זו
עכשיו הנה אם נעביר את 2 כפרמטר נקבל:
2! = 2.1! = 2
באופן דומה, אם נעבור 1 נקבל:
אחד! = 1.0! = 1
אבל אם נעבור 0, זה נשבר
0! = 0. (- 1)! וכאן פקטוריאל -1 אינו מוגדר ולכן זה עובד רק על ערכים> 0
אז עלינו לכתוב שני מקרים
1. n! = n. (n-1)! אם n> = 1
2. 1 אם n = 0
זהו פתרון מלא לכל המספרים השלמים החיוביים ו -0.
תנאי סיום
פונקציה רקורסיבית צריכה למלא תנאי חשוב לסיום. במעבר למצב בו ניתן לפתור את הבעיה ללא רקורסיה נוספת, תסתיים פונקציה רקורסיבית שתמזער את הבעיה לשלבי המשנה הקטנים יותר. רקורסיה יכולה להסתיים בלולאה אינסופית אם לא מתקיים תנאי הסיום בשיחות.
תנאי עובדה:
- גורם של n = n * (n-1) כל עוד n גדול מ- 1.
- 1 אם n = 0
אנו נמיר את תנאי העובדה לעיל בקוד פיתון:
עובדה חסרה (n): אם n == 1: להחזיר n אחר: להחזיר n * עובדה (n-1)
בואו ניקח דוגמא, נגיד שאנחנו רוצים למצוא עובדה של 4:
עובדה (4) # זה יחזיר 4 * עובדה (3) וכן הלאה עד n == 1.
תְפוּקָה: 24
זה משמש לעתים קרובות כל כך כדוגמה לרקורסיה בגלל הפשטות והבהירות שלו. פיתרון של מקרים קטנים יותר של בעיה בכל שלב שהוא מכונה כקורורסיה במדעי המחשב.
מגבלת הרקורסיה של פייתון
בשפות מסוימות ניתן ליצור לולאה רקורסיבית אינסופית, אך בפייתון קיימת מגבלה של רקורסיה. כדי לבדוק את המגבלה, הפעל את הפונקציה הבאה ממודול sys. אשר ייתן את מגבלת הרקורסיה שנקבעה לפיתון.
ייבא sys sys.getrecursionlimit ()
תְפוּקָה: 1000
אתה יכול גם לשנות את המגבלה באמצעות פונקציות setcursionlimit של מודול sys בהתאם לדרישתך, כעת בוא ניצור פונקציה שקוראת לעצמה רקורסיבית עד שהיא חורגת מהמגבלה ונבדוק מה קורה:
def רקורסיבי (): רקורסיבי () אם __name__ == '__main__': רקורסיבי ()
אם אתה מריץ את הקוד שלעיל, תקבל חריג בזמן ריצה: RuntimeError: חריגה מעומק הרקורסיה המרבי. פייתון מונע ממך ליצור פונקציה שבסופה לולאה רקורסיבית בלתי נגמרת.
רישום רשימות עם רקורסיה
דברים אחרים שאתה יכול לעשות באמצעות רקורסיה, למעט פקטוריונים, נניח שאתה רוצה ליצור יחיד מתוך רשימה שמקוננת, ניתן לעשות זאת באמצעות הקוד שלהלן:
def flat (a_list, flat_list = none): if flat_list is none: flat_list = [] for item in a_list: if isinstance (item, list): flat (item, flat_list) else: flat_list.append (item) return flat_list if __name__ == '__main__': מקונן = [1,2,3, [4,5], 6] x = הדפסה שטוחה (מקוננת) (x)
תְפוּקָה: [1,2,3,4,5,6]
הפעלת הקוד שלעיל תביא לרשימה אחת במקום לרשימה שלמה המכילה רשימת מספרים שלמה ששימשנו כקלט. אתה יכול לעשות את אותו הדבר גם בדרכים אחרות, לפייתון יש משהו שנקרא itertools.chain () אתה יכול לבדוק את הקוד המשמש ליצירת שרשרת פונקציות () זו גישה אחרת לעשות את אותו הדבר כמו שעשינו.
יתרונות הרקורסיה
הקוד נקי ואלגנטי בפונקציה רקורסיבית.
ניתן לפרק משימה מורכבת לבעיות משנה פשוטות יותר באמצעות רקורסיה.
יצירת רצף קלה יותר עם רקורסיה מאשר שימוש באיטרציה מקוננת כלשהי.
חסרונות של רקורסיה
לעקוב אחר ההיגיון שמאחורי תפקוד רקורסיבי עשוי להיות קשה לפעמים.
שיחות רקורסיביות יקרות (לא יעילות) מכיוון שהם תופסות הרבה זיכרון וזמן.
קשה לפתוח פונקציות רקורסיביות.
במאמר זה ראינו מהי רקורסיה וכיצד אנו יכולים לפתח פונקציות רקורסיביות מתוך הצהרת הבעיה, כיצד ניתן להגדיר באופן מתמטי הצהרת בעיה. פתרנו בעיה של המפעל וגילינו את התנאים הנדרשים למציאת מפעלים שמהם הצלחנו להמיר את התנאים לקוד פיתון שנותנים לך את ההבנה כיצד פועל רקורסיה. אני חושב שזה מסודר שלפייתון יש מגבלה מובנית לרקורסיה כדי למנוע ממפתחים ליצור פונקציות רקורסיביות בנויות בצורה גרועה. דבר חשוב שחשוב לשים לב אליו הוא שקשיים לאיתור באגים בגלל שהפונקציה ממשיכה לקרוא לעצמה.