רוטר - מבקש עזרה בלימוד רקורסיה

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

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

גירסת הדפסה

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

אשכול מספר 5820

xpman

13:21 30.04.03

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

בעיקר במעקב אחרי שאלות
ובעצים בינאריים

מי שמוכן ללמד אותי את זה
ברמה של 5 יחידות תיכון
אני יודה לו מקרב לב

שתף

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

האשכול	מחבר	תאריך כתיבה	מספר
מכתב	jossepe_4u	30.04.03 13:35	1
הסבר יפה:-)	AlexKarpman	30.04.03 13:53	2
ועוד דוגמא	AlexKarpman	30.04.03 14:00	3
את זה אני יודע פחות או יותר וממש תודה	xpman	30.04.03 14:24	4
אתה מתכוון טבלת מעקב?	jossepe_4u	30.04.03 14:42	5
ואז?	xpman	30.04.03 15:25	6
כן.	szargel	02.05.03 04:42	8
יש מחסנית קריאות.	dryice	30.04.03 15:31	7

jossepe_4u
חבר מתאריך 18.3.02
258 הודעות

13:35 30.04.03

1. מכתב
בתגובה להודעה מספר 0

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

אני ינסה להסביר לך במילים שאני הבנתי את זה

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

מקווה שהבנת

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

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

AlexKarpman

13:53 30.04.03

2. הסבר יפה:-)
בתגובה להודעה מספר 1

בס"ד
לא ממש "פוליטיקלי(מתמטיקלי) קורקט":-)
אבל מסביר את הבסיס די טוב.

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

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

בברכה...

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

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

AlexKarpman

14:00 30.04.03

3. ועוד דוגמא
בתגובה להודעה מספר 0

עבר עריכה לאחרונה בתאריך 30.04.03 בשעה 14:06

בס"ד
מגדלי האנוי:
האגדה אאומרת שאי-שם בודהיסטים(או בראמינים או משהוא) צריך לבצע משימה מסויימת ואז יגיע סוף העולם וכולם יזכור ל"נירוואנה":-)
המשימה היא לעהביר 64 טבעות(אחת גדולה מהשניה) מעמוד אחד לעמוד אחר, תוך שימוש בעמוד שלישי כאשר אפשר להעיבר רק טבעת אחת בכל פעם ואפשר לשים רק טבעת קטנה על גדולה, ולא גדולה על קטנה.
היישום הנפוץ ביותר הינו רקורסיבי.
כדי להעביר N טבעות מ-1 ל-2 בעזרת 3(מספרי העמודים) יש להעביר N-1 מ-1 ל-3 להעביר את הטבעת ה-N מ-1 ל-2 ואז להעביר N-1 טבעות מ-3 ל-2.
כדי להעביר N-1 טבעות מפעילים את האלגוריתם על N-! טבעות(שעכשיו הם N) ועמוד היעד הוא 3(ולא 2) ועמוד ה"עזרה" הוא 2(ולא 3).

לדוגמא:
(1)
1
2
3
(2)
2
3__1
(3)
3__1__2
(4)
__1
3_2

(5)
1__3__2
(6)
_2
1__3

(7)
_1
_2
_3

כל מעבירים 3 טבעות.
פה הפתרון אינטואיטיבי אבל עם 5 טבעות זה מסתבך ועם 20 זה כבר בלתי-אפשרי מעשית בלי מחשב.

בברכה...

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

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

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

xpman

14:24 30.04.03

4. את זה אני יודע פחות או יותר וממש תודה
בתגובה להודעה מספר 0

אבל
השאלה שלי
היא אחרי שמאפסים וחוזרים כאילו להתחלה

מתי יודעים לעבור לשורה שבאה אחרי זאת שמזמנת
ואיך עוקבים אחרי זה

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

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

jossepe_4u
חבר מתאריך 18.3.02
258 הודעות

14:42 30.04.03

5. אתה מתכוון טבלת מעקב?
בתגובה להודעה מספר 4

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

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

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

xpman

15:25 30.04.03

6. ואז?
בתגובה להודעה מספר 5

יש איזה שלב שחוזרים אחורה לא?

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

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

szargel

04:42 02.05.03

8. כן.
בתגובה להודעה מספר 6

חוזרים אחורה בכל השלבים (1.1) (1.2) ו(1.3) באלגוריתם
אתה בעצם מבצע פונקציה, וקורא לעצמה, אני יתן דוגמה בפסקל, אני מקווה שזו השפה שאתם לומדים
Program blah;
Uses Crt;
Var A:Integer;
Function Add(i:integer);
Begin
I:=I+1; {1}
While I<10 do Add(I); {2}
Writeln(I); {3}
End;
Begin {Main}
A:=0;
Add (A);
End.

אני מקווה שאין טעויות קלות, מזמן לא תיכנתתי בפסקל.
מה שהרקורסיה עושה זה להגדיל את I באחד, כאשר הפלט על המסך יהיה המספרים מ10 ועד 1, בסדר יורד
מה שבעצם קורה בתוכנית זה:
בשורה 1- I גודל באחד.
בשורה 2 - בודקים האם I כבר שווה עשר? אם לא, קוראים לפונקציה שוב זה השלב בו "חוזרים"
ואז בעקבות הקריאה לפונקציה בעצם חוזרים לשורה 1.
וככה עד שI לא קטן מ10
ואז מתחילים ליישם את שורה 3 בפונקציה, מדפיסים 10, וסוגרים את הפונקציה, חוזרים לפונקציה הקודמת ומדפיסים 9 וכן הלאה עד 1

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

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

dryice

15:31 30.04.03

7. יש מחסנית קריאות.
בתגובה להודעה מספר 4

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

DRYICE

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

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