בס"ד

אשמח אם מישהו יוכל לכוון אותי בשאלות האלו:
1)להדפיס את סדרת המספרים: 1,1,2,2,3,3,4,4,3,3,2,2,1,1
2)להדפיס את סדרה המספרים: 1,2,3,4,5,6,7,6,4,2
3)כתוב פעולה רקורסיבית המקבלת בסיס b ואת חזרה n ומחזירה b^n.
4)כתוב פעולה רקורסיבית המקבלת 2 פרפמטרים a,b ומחזירה את a פכול b ללא שימוש בפעולת כפל.

תודה לעוזרים!

חג שמח
[התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://math-pl.co.il/forums/images/smilies/smile.gif]

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

קוד:

public void PrintToN(int n)
{
	if(n == 1)
		Console.WriteLine("1");
	else
	{
		PrintToN(n-1);
		Console.WriteLine(n);
	}
}

בס"ד

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

תודה על העזרה וחג שמח

תנסי להתאים את מה שכתבתי לתרגילים שלך:

קחי למשל את תרגיל מספר 3. נרצה לחשב את התוצאה של 2 בחזקת 5 (== 32). מה המקרה הפשוט שבו לא צריך יותר לחשב כלום? מה הפעולה שעבורה צריך 'לבקש טובה'?

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

פתרון תרגיל 1:

קוד:

		void printit(int num)
		{
			if (num == 4)
				Console.WriteLine("4, 4");
			else
			{
				Console.WriteLine("{0}, {1}", num, num);
				a(num + 1);
				Console.WriteLine("{0}, {1}", num, num);
			}
		}

מה שקורה בעצם זה שבהתחלה יוצג 1,1, 2,2, 3,3, ואח"כ כשזה יגיע ל4,4, אין קריאות רקורסיביות נוספות ולכן שאר הקוד בהתאמה יתבצע ויוצג 3, 3, 2, 2, 1, 1.

תרגיל 2:
די מבוסס על התרגיל הקודם, יתבצע בצורה הבאה:

קוד:

		void print(int num)
		{
			if (num == 7)
				Console.WriteLine("7");
			else
			{
				Console.WriteLine("{0}", num);
				a(num + 1);
				if(num % 2 == 0)
					Console.WriteLine("{0}", num);
			}
		}

אין ממש הבדל חוץ מהתנאי שהוספתי שהכרחי לסדרה.

תרגיל 3:

קוד:

int pow(int a, int b)
{
 if(b == 0)
   return 1;
 return a * pow(a, b - 1);
}

אני אתן דוגמא למה שקורה:

קוד:

pow(3, 2)

3 * pow(3, 1)
 3 * pow(3, 0)
  1 is returned
 3 * 1 = 3 is returned
 3 * 3
ואין קריאות נוספות לפונקציה ולכן מוחזר הערך.

התרגיל הזה גם הוא די דומה לתרגיל הקודם:

קוד:

int multiply(int a, int b)
{
 if(b == 1)
  return a;
 return a + multiply(a, b - 1);
}

דוגמא להמחשה:

קוד:

multiply(3, 3)

3 + multiply(3, 2)
 3 + multiply(3, 1)
   3 is returned
 3 + 3
 3 + 6
אין עוד קריאות נוספות ולכן יוחזר הערך.

בס"ד

תודה תודה ותודה רבה לך.
עזרת לי מאוד.
את התרגיל השלישי והרביעי הבנתי.
לגבי התרגיל הראשון שזה מדפיס 4 ו - 4 אז לא הבנתי אחרי זה איך זה מגיע ל 3 ו - 3 ...?
לגבי התרגיל השני לא הבנתי איך זה מגיע ל - if השני?

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

תודה רבה על העזרה!

חג שמח

?

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

בס"ד

אבל איך זה הגיוני הוא מדפיס 4,4 ואז איך הוא מגיע ל - else. הרי הוא סיים את ה - if של 4,4 ומה ה- else קשור אחרי זה?
ככה זה בפעולות רקורסיביות? או שזה ככה תמיד?
בחיים לא נתקלתי בדבר כזה חוץ מפעולות רקורסיביות.

תודה על העזרה.

שבוע טוב

קוד:

printit(1) ->
 Console.WriteLine("{0} {1}", 1, 1);
  printit(2) ->
   Console.WriteLine("{0}, {1}", 2, 2);
   printit(3) ->
		  Console.WriteLine("{0}, {1}", 3, 3);
		  printit(4) -> Console.WriteLine("{0}, {1}", 4, 4); // no more recursive calls!
		  Console.WriteLine("{0}, {1}", 3, 3);  // מכאן ימשיכו כל אחת מהפונקציות
	Console.WriteLine("{0}, {1}", 2, 2);
  Console.WriteLine("{0}, {1}", 1, 1);

בס"ד

הבנתי.

תודה רבה על העזרה!

שבוע טוב