רוטר - יש מצב שמישהו ילמד אותי ריכורסיה בעיצוב תוכנה

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"יש מצב שמישהו ילמד אותי ריכורסיה בעיצוב תוכנה"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #5257	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 5257

Eraner

00:29 03.03.03

יש מצב שמישהו ילמד אותי ריכורסיה בעיצוב תוכנה

אין זה לא מובן לי בבקשה מישהו

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
הסבר מהיא רקורסיה	gad	03.03.03 00:39	1
אחי אפשר את האיסיקיו שלך בבקשה	Eraner	03.03.03 00:42	2
קשה לי קצת להסביר דרך המחשב	יהונתן	03.03.03 00:58	3
נראה לי שסיבכת אותו	gad	03.03.03 01:03	4
רקורסיה:	dryice	03.03.03 12:11	5
האם יש צורך ברקורסיה?	avi885	03.03.03 12:18	6
אכן בחישוב עצרת, אין צורך ברקורסייה...	Dudenland	03.03.03 13:50	7
לפעמים היא חיונית, למשל minimax,dfs	dryice	03.03.03 17:51	8

gad

00:39 03.03.03

1. הסבר מהיא רקורסיה
בתגובה להודעה מספר 0

רקורסיה היא מצב בה תוכנית קוראת לעצמה
אם תרצה דוגמאות תגיב
גד

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Eraner

00:42 03.03.03

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

אני לא אקרצץ לך מבטיח אתה יכול?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

יהונתן

00:58 03.03.03

3. קשה לי קצת להסביר דרך המחשב
בתגובה להודעה מספר 0

אבל אני יכול לתת לך דוגמא פשוטה שעשויה לעזור.
אלגוריתם:

(*)הפוך()....................................שם הפונקציה
(1)קלוט מספר -> משתנה............המשתנה הינו char (תו).
(2)אם משתנה שונה מ "." אזי
...(2.1)הפוך()
(3)הדפס משתנה

מה שקורה פה הוא כדלהלן: קולטים מספר אל תוך משתנה מסויים.
אם המשתנה אינו נקודה, כלומר אינו סוף המשפט הפונקציה "הפוך()" נקראת שוב
רק אל תתבלבל! המשתנים שונים! למשל אם השתמשת באות A לשם המשתנה אז אם
תקרא שוב לפונקציה המשתנה A החדש לא קשור כלל לקודם. העיקרון של רקורסיה
הוא ניצול העובדה שכל עוד המחשב לא הגיע אל סוף הפונקציה המשתנים שלה לא
נמחקים לכן כשתקלט נקודה המחשב יסיים את הפונקציה בה הוא נמצא שהיא
האחרונה לה הוא קרא.
ומה יקרה? תודפס הנקודה כי הוא מדלג לפקודה האחרונה. ואז בסוף הפונקציה
המחשב יחזור לאן? למקום ממנו הוא קרא לפונקציה קודם כלומר לשורה 3 של
הקריאה הקודמת לפונקציה. שם הוא צריך להדפיס משתנה. איזה משתנה הוא
ידפיס? כמובן את התו שנקלט לפני הנקודה וכן הלאה עד סגירת כל הפונקציות.
לדוגמא:
אם הקלט היה .Hello there אז הפלט יהיה ereht olleH. מבין?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

gad

01:03 03.03.03

4. נראה לי שסיבכת אותו
בתגובה להודעה מספר 3

הוא בקושי מבין פסקל
תן לו דוגמה של כפל רקורסיבי או חזקה רקורסיבית ולא משהו מושפט
להית'
גד

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

12:11 03.03.03

5. רקורסיה:
בתגובה להודעה מספר 0

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

function Atzert(n : integer): integer;
begin
if n==0 Atzert:=1
else Atzert:=Atzert(n-1)*n;
end;

חישוב עצרת של מספר n הוא מכפלת כל המספרים השלמים מ1 עד n כאשר
עצרת של אפס מוגדר להיות 1. אנו מסתמכים על התכונה של עצרת שלכל n טבעי:
n!=(n-1)!*n
כאשר הפונקציה רוצה לחשב עצרת של 5, היא ראשית תחשב עצרת 4 בהנחה
שהיא תצליח לחשב עבור 4, היא תכפיל ב 5, ותוציא פלט נכון עבור עצרת
של 5. כדי לחשב עצרת 4 היא צריכה לחשב עצרת של 3 וכן הלאה.
תנאי העצירה שלנו הוא n==0 שם אנחנו לא מבצעים קריאה רקורסיבית אלא
פשוט מחזירים ערך נכון(עצרת של 0 היא 1)
חישוב ברקורסיה הוא שקול למעשה להוכחה באינדוקציה, שי לנו בסיס לאינדוקציה שזה תנאי העצירה, ויש לנו צעד האינדוקציה שזה הקשר
בין ערך הפונקציה על קלט גדול לבין ערך הפונקציה על ערכים קטנים
במקרה שלנו: n!=(n-1)!*n

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

avi885

12:18 03.03.03

6. האם יש צורך ברקורסיה?
בתגובה להודעה מספר 5

עבר עריכה לאחרונה בתאריך 03.03.03 בשעה 12:21

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

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Dudenland

13:50 03.03.03

7. אכן בחישוב עצרת, אין צורך ברקורסייה...
בתגובה להודעה מספר 6

עבר עריכה לאחרונה בתאריך 03.03.03 בשעה 13:54

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

Dudenland

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

17:51 03.03.03

8. לפעמים היא חיונית, למשל minimax,dfs
בתגובה להודעה מספר 6

כדי לפתור משחקי סכום אפס, אנו בונים עץ מהלכים.
ואנו בונים אותו ועוברים עליו באופן רקורסיבי,
בכלל על עצים יש המון דברים שעושים בסדר DFS ונוח מאוד לעשות
ברקורסיה. לא רק שנוח מאוד לעשות ברקורסיה אלא שפתרונות לא
רקורסיבים נוטים להיות ארוכים ומכוערים ו/או בסופו של דבר
מה שיש זה מימוש משלך של דמויי מחסנית, ורקורסיה משלך.
כמובן שכל מה שניתן לממש בעזרת רקורסיה, ניתן לממש בעזרת מערך
ולולאות. אבל זה כמעט תמיד מיותר לחלוטין.
במקרים מסויימים כשהיעילות מאוד קריטית, ולפונקציה הרקורסיבית
שכתבנו יש הרבה פרמטרים והרבה משתנים לוקאליים, אז לפעמים עדיף לממש
את המחסנית בעצמך(אבל יש פתרונות אחרים גם בתוך מנגנון הרקורסיה
שיקטינו את כמות המידע על המחסנית)
יש אנשים שכותבים רקורסיה לא יעילה, משום שזה יותר יפה ויותר ברור
ויותר קל לקרוא ויותר קל לכתוב. וזה בסדר גמור, ולרוב שיקולים
אלה הרבה יותר חשובים מזמן ריצה.
יש הרבה מקומות(כמעט כל מה שאני כותב, בין השאר) שבהם משתמשים ברקורסיה
באופן יעיל, וניסיון לממש ללא רקורסיה, יהיה קשה מאוד, יכיל באגים,
ובסופו של עניין, לא יהיה יעיל יותר.
ושוב: מימוש קריא הוא כמעט תמיד עדיף על מימוש יעיל. וודאי וודאי כשהפרש
המהירות זניח. זאת טעות מאוד נפוצה, שאנשים מנסים לייעל קוד,
הם בסופו של דבר קיצרו את זמן הריצה של התוכנה ב100 פעימות,
והפכו אותה לבלתי קריאה בעליל.
דוגמא קלאסית לשימוש לא יעיל ומיותר ברקורסיה, הוא חישוב פיבונאצ'י
חישוב האיבר הi בסדרה, לוקח בפתרון סדרתי נאיבי O(N) בפתרון הרקורסיבי
הנאיבי זה לוקח זמן אקספוננציאלי, וזה סתם משום שמחשבים דברים פעמים רבות.

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד