שיחה:רקורסיה

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

כדי לחשב את ערך האיבר n בסדרת פיבונאצ'י, הפונקציה קוראת לעצמה פעמיים - עבור n-1 ועבור n-2. כל אחת משתי קריאות אלו תקרא לפונקציה פעמיים נוספות, וכך הלאה... - כלומר, במקום האלגוריתם האיטרטיבי שלו סיבוכיות לינארית - $\ O(n)$, ניתן כאן אלגוריתם בעל סיבוכיות מעריכית - $\ O(Fib(n))\approx O(\phi ^{n})$ !!

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

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

Naftali

---

איתי:

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

---

אם לדייק, לנוסחה הסגורה, $F(n)={\varphi ^{n} \over {\sqrt {5}}}-{(1-\varphi )^{n} \over {\sqrt {5}}}$, קיימת סיבוכיות, והיא, כמובן, $O(1)$.

חישוב רקורסיבי של איבר בסדרת פיבונאצ'י הוא דוגמה מעולה, בגלל שהוא מאוד אינטואיטיבי (ממש על־פי ההגדרה: כל מספר הוא סכום שני קודמיו, למעט $F(0)=F(1)=1$) ומדגים באופן יפה את עקרון הרקורסיה.

--The Fool 14:40, 18 פבר' 2004 (UTC)

---

לא השתכנעתי.

הקוד שבדוגמא לא פועל עבור ערכי n הגדולים מ-70. דוגמת קוד כזו מתאימה לקורס פסקל לילדים, לא לאנציקלופדיה.

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

Naftali 15:21, 18 פבר' 2004 (UTC)

---

איתי:

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

באשר לדוגמא, בינתיים זה 2:1 לטובתה. זה לא דוגמא לסיבוכיות, זה דוגמא לרקורסיה.

איך אני חותם עם השם משתמש שלי ותאריך?

---

לנפתלי: קודמקול, לא הייתי מזלזל בפסקל או בילדים (טוב, נו, אולי בפסקל...). העובדה שגודלו של int מוגבל לא קשורה כלל לדוגמה: גם הבעיות שהזכרת תפולנה על n־ים מספיק גדולים.

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

לאיתי: הוסף את המחרוזת הבאה בסוף ההודעה: --~~~~ .

--The Fool 15:43, 18 פבר' 2004 (UTC)

---

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

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

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

כדי לחתום את השם עם תאריך אתה פשוט כותב ארבע טילדות: ~~~~.

Naftali 15:48, 18 פבר' 2004 (UTC)

---

כדאי להפריד בין פונקציות רקורסיביות (פיבונאצ'י היא דוגמה מצויינת) לבין אלגוריתמיקה רקורסיבית. ישנם גם תחומים נוספים שנכנסים תחת ההגדרה "רקורסיה". כדוגמה לערך איכותי על רקורסיה, ראו את הערך המקביל באנגלית - Recursion. אני חושב שכדאי לתרגם חלקים נכבדים ממנו. Naftali 22:21, 18 פבר' 2004 (UTC)

---

חשבתי להוסיף את ptr* במטרה להדגים רקורסיה מנקודת־מבט אומנותית, אבל יש בעיה: זכויות היוצרים על הציורים של אשר מגבילים את השימוש בהם.

אני די בטוח שבקישור לתמונה אין כל בעיה חוקית. השאלה היא האם הטבעת התמונה ממקור חיצוני נחשבת כרפרודוקציה, כי היא מופיעה, לכאורה, כחלק מוויקיפדיה; או שלא, כי התמונה עצמה מאוכסנת בשרת אחר, ואינה חלק אינטגראלי מהדף בוויקיפדיה, אלא רק הוראה ל־browser לקרוא את התמונה מהשרת המרוחק.

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

--The Fool 20:33, 2 מרץ 2004 (UTC)

לא נראה לי שהתמונה שאתה מדבר עליה מבטאת רקורסיה Effib

זוהי רקורסיה הדדית במובהק: כמו שפונקציה a קוראת לפונקציה b ופונקציה b קוראת לפונקציה a, כך היד האחת מציירת את רעותה, וזו מצידה מציירת את הראשונה.

אפשר לנסח את זה כך, ב־Pseudo-C++/Pseudo-Java: תהי Hand מחלקה ובה מוגדרת הפונקציה (void draw(object target. בתוכנית עצמה נכתוב:

Hand h1, h2;
h1.draw(h2);
h2.draw(h1);

--The Fool 21:59, 2 מרץ 2004 (UTC)

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

---

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

דיבורים על סיבוכיות רק מסבכים עוד יותר את החיים להדיוטים. אנחנו רוצים להסביר מה זה רקורסיה, לא איך משתמשים בצורה יעילה ברקורסיה. להתווכח על כך שהדוגמא לא רצה מעל n מסויים זו ממש קטנוניות, כי זה תלוי במערכת ההפעלה שעליה מריצים את התוכנה. אגב, גם בצורה איטרטיבית הקוד יפסיק לפעול פתאום, כשהמשתנים שלך לא יהיו מספיק גדולים כדי להכיל את המידע - טכני לגמרי. חייבים להפריד כאן בין עיקר וטפל, והעיקר הוא להראות בצורה הפשוטה ביותר האפשרית את הרעיון שעומד מאחורי רקורסיה. גדי אלכסנדרוביץ' 06:51, 3 מרץ 2004 (UTC)

אתה יכול לתעד את הקוד, You know אבי 13:18, 23 מרץ 2005 (UTC)

---

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

כדי לחשב את המספר ה-100 בסדרת פיבונאצ'י (וזה בהחלט אפשרי, במהדרים התומכים ב-Int64), פונקציה איטרטיבית תבצע 100 מחזורים, ואילו הפונקציה הזו תקרא לעצמה 894,337,526,674,457,401,000 פעמים! הפונקציה הזו לא תעצור עם הודעת שגיאה על Overflow, אלא פשוט תפעל עד שהמחשב יכובה, או במקרה הטוב - עד שתיגמר לו המחסנית. (תחשוב על ההדיוט המסכן שיחפש באינטרנט קוד לחישוב מספר פיבונאצ'י, והמחשב שלו יתקע או יקרוס בלי הסבר!)

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

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

Naftali 07:54, 3 מרץ 2004 (UTC)

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

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

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

Naftali

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

---

הערה לגבי המרה בין פיתרון רקורסיבי לאיטרטיבי

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

לא משנה

לדעתי אתה טועה. לא זה ההבדל בין פונקציות שניתנות להמרה לאיטרטיביות לבין אלו שלא.

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

Naftali 10:59, 3 מרץ 2004 (UTC)

GNU

קראתי פעם בפי. סי. מגזין ש-GNU זה Gee, not unix, כך שזו לא רקורסיה. אבי 12:00, 3 מרץ 2005 (UTC)

האתר הרשמי ([1]) טרם שמע על השגותיו של פי סי מגזין. גדי אלכסנדרוביץ' 13:46, 3 מרץ 2005 (UTC)

OK אבי 15:27, 3 מרץ 2005 (UTC)

מישהו חמד לצון?

זה רק נדמה לי או שמישהו חמד לצון ושתל את הערך רקורסיה תחת ראו גם? בברכה Shayakir 17:56, 22 מרץ 2005 (UTC)

אני הפושע. זוהי דוגמה לרקורסיה. אבינעם 18:05, 22 מרץ 2005 (UTC)

זו דוגמה טובה...בברכהShayakir 18:11, 22 מרץ 2005 (UTC)

תודה. אבינעם 10:01, 23 מרץ 2005 (UTC)

מצחיק גם בפעם העשירית. אמיתי 11:18, 23 מרץ 2005 (UTC)

הרעיון נלקח מבדיחה שמופיעה באינדקס של ספר ה-C (שפת תכנות). אפשר לראות אותה (ועוד בדיחות טובות) באתר של משתמש:Tal Cohen Book In-Jokes. אבינעם 12:49, 23 מרץ 2005 (UTC)

נראה שמישהו דאג להסיר את ההלצה, האם כדאי להחזיר אותה (או לפחות לפתוח את הערך כך: "רקורסיה (Recursion) היא תופעה שכל מופע שלה מכיל מופע נוסף שלה")? Tahmar1900 19:14, 26 בינואר 2007 (IST)

הערות והשגות על הערך רקורסיה

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

יש לי כאן השגה אחת עקרונית ובנוסף כמה הערות קטנות יותר. ההשגה העקרונית היא בעניין ההתיחסות הרחבה שיש בערך הזה לנושא "תופעות רקורסיביות". עד כמה שידוע לי, ועל פי כל הבדיקות שערכתי במקומות שונים, המושג "תופעה רקורסיבית" אינו מוכר בעולם. רקורסיה היא מונח שמקורו במתמטיקה ובהמשך מדעי המחשב. ההתיחסות היחידה למונח recursive phenomena שמצאתי באינטרנט הוא בהתיחסות לעבודת מחקר בחינוך שנעשה על-ידי דלית לוי מהוראת המדעים בטכניון, שדיבר על איתור תופעות אלו בטבע. צריך לדעתי לאחד את כל הסעיפים על רקורסיות חזותיות/תודעתיות/לשוניות/משפטיות תחת סעיף אחד: "תופעות רקורסיביות" ולהעביר אותן יותר למטה.

מעבר לזה, כמה הערות נקודתיות:

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

--סלע 22:51, 23 מרץ 2005 (UTC)

• לרוב משתמשים בעברית במילה מעגלי ולא רקורסיבי ולכן לא מצאת כלום בגוגל. זה אותה משמעות בדיוק.
• גם אני לא שמעתי על רקרוסית עצירה, כך שזה באמת מוזר. טרול רפאים 22:56, 23 מרץ 2005 (UTC)

לא. מעגלי ורקורסיבי זה לחלוטין לגמרי ממש ממש לא אותו דבר. רקורסיה היא מושג מתמטי שיש לו משמעות מאד מוגדרת. רקורסיה היא הגדרה עבור איברים בקבוצה, כאשר כל איבר בקבוצה מוגדר כפונקציה של איברים קודמים באותה קבוצה (בהנחה שקיים יחס סדר בין האברים). לכן ההגדרה "יהודי הוא מי שאימו יהודיה" (פלוס ה"גרעין": שרה אימנו היא יהודיה, אם רוצים שהרקורסיה תעצור) היא רקורסיבית, ואילו ההגדרה "רקורסיה היא תופעה שמתקיימת בה רקורסיה" היא הגדרה מעגלית אבל לא רקורסיבית. הבילבול הזה בין מעגלי לרקורסיבי הוא באמת אחת מהבעיות העיקריות בערך הזה. --סלע 16:58, 24 מרץ 2005 (UTC)

בתיאוריה אתה צודק, בפועל לא. אם תסתכל על הפעמים שבהם משתמשים במילה מעגלי תראה שחלק גדול מהם מתייחס למעשה לרקרוסיבי. טרול רפאים 17:05, 24 מרץ 2005 (UTC)

אתה יכול להסביר ו/או להדגים? לא מצאתי לטענה שלך כל תימוכין. --סלע 17:27, 24 מרץ 2005 (UTC)

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

PNG הוא PNG Not GIF?

עד כמה שידוע לי, PNG הוא Portable Network Graphics. rotemliss – שיחה 06:48, 17 אפר' 2005 (UTC)

נדמה לי ששמעתי בהרצאה של ריצ'ארד סטולמן שבמקור זה היה באמת png's not gif ולאחר מכן הפורמט קיבל שם יותר גנרי. הפורמט באמת נוצר על מנת להוות אלטרנטיבה ל gif המשתמש באלגוריתם דחיסה המוגן בזכויות פטנט (LZ)

יש דוגמאות רבות לשמות רקורסיביים של האקרים כמו pine is not emacs

יש גם דוגמה לרקורסיה הדדית herd (לא זוכר את הפרטים)

יש דוגמה מבריקה במיוחד של שמות לעורכים הקרויים "אחד" ו"שניים" בגרמנית. מי שזוכר את הפרטים אולי יוכל להשלים. אורי מוסנזון 07:08, 17 אפר' 2005 (UTC)

בשביל הפרוטוקול:

The GNU Hurd project is named with a mutually-recursive acronym: "GNU" stands for "GNU's Not UNIX", "Hurd" stands for "Hird of Unix-Replacing Daemons," and "Hird" stands for "Hurd of Interfaces Representing Depth." (מהויקי האנגלית) פכידרם 13:46, 8 ספטמבר 2005 (UTC)

דוגמאות לרקורסיה

כתוב בערך כך: "גם השם זלמן שז"ר הוא דוגמא לרקורסיה - שז"ר הם ראשי התיבות של שמו המלא, שניאור זלמן רובשוב". מישהו מתנדב להסביר למה זו רקורסיה? (זה יותר דומה ל"רחוב המלך King George").

מחקתי את הדוגמה של שז"ר, לאחר שקיבלתי את דבריך. ובמחשבה שניה עולה בדעתי האפשרות, שאולי זו רקורסיה לשונית הדדית, 'שז"ר' מכיל את שמו המלא, 'שניאור זלמן רובשוב'. ו'שניאור זלמן רובשוב' מכיל את ראשי התיבות שלו 'שז"ר'. אם רעיון זה יתקבל על דעת מישהו נוסף, אחזיר את הדוגמה, תוך ציון כי זוהי דוגמה לרקורסיה לשונית הדדית. (ציון שהיה חסר קודם). מלח השמים 20:23, 5 מאי 2005 (UTC)

המשתמש שתרם את דוגמת שז"ר, החזיר אותה לערך. הזמנתי אותו להשתתף כאן בדיון. ואגב, אם שז"ר נחשב ל'רקורסיה לשונית הדדית', אז כך גם כל ראשי תיבות וא"כ זו שאלה כללית יותר. מלח השמים 15:29, 9 מאי 2005 (UTC)

"זלמן שזר" הוא בוודאות לא רקורסיה, שכן אחרי "פתיחה" ראשונה שלו (של ראשי התיבות), לא ניתן להמשיך ולהתקדם איתו: "זלמן שזר" => "זלמן שניאור זלמן רובשוב". אילו המילה שזר הופיע בראשי התיבות עצמן, אז היה זה רקורסיה. Yonidebest Ω Talk‏ 13:55, 8 ספטמבר 2005 (UTC)

מול משתמשים אנונימיים שתרמו משהו מפוקפק, קודם כל מוחקים ואחר כך מתדיינים, מבררים, שואלים, פונים, מתעניינים. לא נעים, אבל אחרת זרקתם לפח את אמינות ויקיפדיה והבאתם לעולם את הבן המאומץ של אריק שרון. שש"ז 11:25, 8 ספטמבר 2005 (UTC)

לענ"ד לא נראה רקורסיה ולא בן של רקורסיה. מה דעתכם על הסרטים שבהם נתקעים בזמן, הולכים לישון וקמים כל פעם מחדש באותו יום, עד שעושים משהו שמפסיק את העניין, (כמו תנאי בפונקציה רקורסיבית). האם זוהי דוגמה לרקורסיה? --אפי ב. • שיחה • 12:29, 8 ספטמבר 2005 (UTC)

זה נראה לי סתם כהליכה במעגל שש"ז 13:41, 8 ספטמבר 2005 (UTC)

שנינות

מישהו אמר פעם(להלהן כביכול הגדרת הערך המילוני של רקורסיה) : "רקורסיה: עיין ערך רקורסיה... אם הבנת -צא!". בעיני זו שנינות ...

דוגמאות בערך

"רקורסיה לשונית מסוג אחר היא הברכה "צרור ברכות ואיחולים", בה המברך אינו מציין בפועל ברכה או איחול מפורשים". מדוע ולמה זו רקורסיה? עוזי ו. 01:27, 24 מאי 2006 (IDT)

כיוון שהברכה הפנימית יכולה להיפתח ל"צרור ברכות" שוב ושוב באופן רקורסיבי. Gil mo 01:30, 24 מאי 2006 (IDT)

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

יותר נכון, רקורסיה עם תנאי קצה. גם השיטה הרקורסיבית לחישוב מספרי פיבונאצ'י היא כזו. יבחרו-נא המברך או המבורך את הקצה בעצמם. אני בניגוד אליך מקפיד להתכוון שכל הברכות תהיינה "צרור ברכות ואיחולים" :) Gil mo 01:45, 24 מאי 2006 (IDT)

זו רקורסיה אם ורק אם הברכות בצרור עשויות להיות "צרור ברכות" בעצמן. אני חושב שזו דוגמא מבלבלת וכדאי להסיר אותה. עוזי ו. 01:49, 24 מאי 2006 (IDT)

הן אכן עשויות להיות "צרור ברכות" בפוטנציה. אם אתה (ואחרים) סבורים שהדוגמא לא מתאימה אתה רשאי להסירה. ליל מנוחה Gil mo 01:52, 24 מאי 2006 (IDT)

אולי אפשר לחשוב על "ברכה" בתור משתנה בדקדוק חסר הקשר, ועל "צרור ברכות" כעל משתנה שיכול לגזור את עצמו ועוד ברכה. גדי אלכסנדרוביץ' 08:11, 24 מאי 2006 (IDT)

"לוח סודוקו"

השיטה שמציעים בערך לפתרון לוח סודוקו באמצעות רקורסיה הוא פשוט דוגמה סטנדרטית לשיטת Backtracking. אותה שיטה מאפשרת לפתור מבוכים, מערכת משוואות מעל שדה סופי, וכו'. לדעתי כדאי להסביר את השיטה באופן כללי, ולא לתת דוגמאות שכאלו (להבדיל, הפתרון של מגדלי האנוי באמצעות רקורסיה אינו Backtracking, והוא המחשה נאה לכוחה האמיתי של רקורסיה). גדי אלכסנדרוביץ' 12:39, 5 בינואר 2007 (IST)

עץ תיקיות

ניסיתי להבין ללא הצלחה מה רקורסיה בעץ התיקיות שמוצגות בדף. אולי יש משהו יותר מוכשר שיוכל להסביר את העניין. תודה ישראל פלד 20:34, 21 בינואר 2007 (IST)

חיפוש קובץ בתיקיות יכול להתבצע באופן רקורסיבי: בדוק האם הקובץ נמצא בתיקיה הנוכחית, ואם לא, הפעל את אלגוריתם החיפוש על כל אחת מתת התיקיות. גדי אלכסנדרוביץ' 20:37, 21 בינואר 2007 (IST)

ההגדרה האולטימטיבית לרקורסיה

כאן רקורסיה

איתן 01:10, 23 ביוני 2007 (IDT)

זה בפירוש לא נכון. הגדרה זו היא לולאה אינסופית, בניגוד לרקורסיה, שבה יש תנאי עצירה. דוד שי 08:01, 23 ביוני 2007 (IDT)

ראשית, המטרה היתה להביא קצת הומור לדיון.

שנית, אם מה שאתה אומר נכון אז צריך למחוק חצי מהערך. אבל גם על סמך הכתוב "רקורסיה אינסופית" יש רקורסיות שהן אין סופיות. איתן 11:04, 23 ביוני 2007 (IDT)

הומור זה בסדר, כל זמן שהוא מדויק ונכון.

אכן, ברקורסיה אינסופית (שמשולש סרפינסקי ופרקטלים אחרים הם המחשה נאה שלה), אין תנאי עצירה - העניין נשמט מזכרוני בעת כתיבת תגובתי. עדיין, גם ברקורסיה אינסופית יש התקדמות. דריכה במקום, כפי שמתקיים בבדיחה, היא סוג טריוויאלי של רקורסיה אינסופית. דוד שי 11:20, 23 ביוני 2007 (IDT)

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

אז להלן ההגדרה האולטימטיבית ל לולאה אינסופית איתן 12:35, 23 ביוני 2007 (IDT)

תנאי עצירה הוא לא חלק מהרקורסיה עצמה אלא תוספת. רקורסיה היא קריאה של פונקציה לעצמה ולכן היא סג של לולאה אינסופית. קקון 13:33, 23 ביוני 2007 (IDT)

גם אצלנו הייתה פעם בדיחה דומה (תחת ראו גם בגרסה הזאת למשל) ‏ costello • ‏ שיחה 13:42, 23 ביוני 2007 (IDT)

קוד תכנותי

בעבר שמתי דוגמה לקוד תכנותי קצר לרקורסיה עם הסבר לאלו שאינם מבינים בעניין וראיתי שהוא נמחק. האמנם אין מקום בערך לקוד תכנותי שימחיש רקורסיה. בדקתי בערכים בשפות אחרות וראיתי שברובם יש קודים תכנותיים. ועד ההצלה הישראלי למען הקוד התכנותי קורא להחזיר אותו לערך רקורסיה. --אפי ב. • שיחה • 09:27, 10 ביולי 2007 (IDT)

רקורסיות לשוניות בעברית?

לא הבנתי איך שינה בשבת תענוג זו רקוסיה, זה קצת כמו המקרה של זלמן שזר שמופיע בשיחה למעלה. זה עוד מילא, "צדיק כתמר יפרח" כסופי תיבות של קורח זו רקורסיה?! בברכה, סתם עומר • שיחה 00:02, 11 ביולי 2007 (IDT)

בגלל שמדובר בהגדרה אינסופית, על התשובה מהי שבת - אתה מקבל את ההסבר - שינה בשבת תענוג. ואתה חוזר אל השאלה מהי השבת וחוזר חלילה. --אפי ב. • שיחה • 00:09, 11 ביולי 2007 (IDT)

זו הגדרה מעגלית, לא רקורסיה. ‏odedee • שיחה 00:31, 11 ביולי 2007 (IDT)

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

שבת = שינה בשבת תענוג = שינה בשינה בשבת תענוג תענוג = שינה בשינה בשינה בשבת תענוג תענוג תענוג, וכך הלאה עד אין קץ. דוד שי 06:28, 11 ביולי 2007 (IDT)

תמונה

אגב לאחרונה נוצרה לי רקורסיה מעניינת. נכסתי בתוכנת שליטה מרחוק למחשב של חבר, שבאותו הזמן נכנס למחשב שלי באותה תוכנה, והתקבלה רקורסיה הדדית כמו בשתי מראות בשני המחשבים. אשתדל בקרוב לשחזר ולהביא תמונת מסך. --אפי ב. • שיחה • 10:56, 11 ביולי 2007 (IDT)

האם רקורסיה היא סוג של רדוקציה?

הועבר משיחת משתמש:אורי מוסנזון

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

כך אני מבין זאת: אלגוריתם רקורסיבי פותר בעיה ע"י פתרון בעיה אחרת, פשוטה יותר אבל מאותו סוג. פתרון בעיה אחת בעזרת פיתרון של בעיה אחרת זה רדוקציה, לא? אורי מוסנזון - שיחה 03:13, 1 בדצמבר 2009 (IST)

אלגוריתם רקורסיבי פותר בעיה ע"י שימוש באותו האלגוריתם, כאשר בכל קריאה רקורסיבית האלגוריתם יקבל קלט נתונים שונה, "פשוט" יותר, ה"מתקרב" יותר ויותר לתנאי העצירה של הרקורסיה. מספר הקריאות הרקורסיביות איננו קבוע, ולרוב תלוי בגודל קלט הנתונים המקורי. אני מקווה שכעת ההבדלים בין שני המושגים ברורים יותר. רוזבאד - שיחה 23:49, 1 בדצמבר 2009 (IST)

רדוקציה היא פתרון בעיה ע"י פיתרון בעיה אחרת. אתה טוען שברקורסיה, לא מדובר בבעיה אחרת כי ההבדל הוא רק בנתונים ולא באלגוריתם הפיתרון. אתה חושב שהמושג רדוקציה מתייחס למחלקות שקילות של בעיות לפי אלגוריתם הפיתרון שלהם. אולי אתה צודק. אם כן, אולי כדאי לחדד את העניין בערך רדוקציה ולהגיד בדיוק למה הכוונה בבעיה "אחרת". אורי מוסנזון - שיחה 07:43, 2 בדצמבר 2009 (IST)

יש מושג של "רדוקציה עצמית", שהוא למעשה זהה למושג הרקורסיה שעליו מדובר כאן. עם זאת, להגיד שברקורסיה אלגוריתם הפתרון הוא אותו דבר זו קצת רמאות - תמיד יש לנו לפחות שני אלגוריתמים (אחד למקרים "גדולים" ואחד למקרים "קטנים") שכרוכים יחד עם הוראת if מלאכותית (הדמיון הוא במטרה המשותפת שלהם). בנוסף, יש גם רקורסיות מתוחכמות יותר (A קורא ל-B שקורא ל-A) שבהן לא ברור שאפשר לראות כלל את ההגיון הזה, כך שרקורסיה באופן כללי מתוארת באמצעות הקונספט של פונקציה שמסוגלת להופיע פעמיים במחסנית הקריאות (משהו שצריך להתחשב בו כשמממשים את השפה - למשל, זו סיבה מדוע צריך בכלל מחסנית קריאות). 07:47, 2 בדצמבר 2009 (IST)

―gadial (שיחה | תרומות | מונה) לא חתם ‌ 00:00, 10 בינואר 2000 (IST)

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

מעניין, אני דווקא הבאתי את זה כדוגמה למקרה שבו רקורסיה איננה בדיוק רדוקציה. גדי אלכסנדרוביץ' - שיחה 08:58, 2 בדצמבר 2009 (IST)

זהו, עכשיו התבלבלתי לגמרי.. אתה דיברת על כך שהאלגורתים שמופעל בקריאה הרקורסיבית שונה מזה של הבעיה המקורית. אם כך, לא מדובר ברדוקציה עצמית אבל עדיין ברדוקציה, לא?אורי מוסנזון - שיחה 09:11, 2 בדצמבר 2009 (IST)

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

עוד דרך להצגת רדוקציה: "קיימת בעיה א', ולה פיתרון ידוע בסיבוכיות ברורה. כעת, אנחנו רוצים לפתור את בעיה ב', אך מתקשים למצוא פיתרון או להוכיח את הסיבוכיות של הפיתרון שמצאנו. לפיכך, נשתמש ברדוקציה של בעיה ב' לבעיה א', ואז כל שנצטרך להוכיח הוא את נכונות הרדוקציה ואת הסיבוכיות שלה, וכך מצאנו פיתרון לבעיה ב'". בהצגה כזו של רדוקציה ברור שבעיה א' איננה נפתרת באמצעות פיתרון בעיה ב', ובעיה ב' איננה נפתרת באמצעות אותה הבעיה תוך שימוש בקלט אחר. אין כאן שום רקורסיה הדדית, ואין כאן שום רדוקציה עצמית. רוזבאד - שיחה 21:04, 2 בדצמבר 2009 (IST)

דקויות הניסוח שלך חומקות ממני. אני לא מבין מה ההבדל המהותי בין מה שכתבת ומה שאני כתבתי (פרט לכך שאתה "מציג" רדוקציה באמצעות שימוש במילה רדוקציה - זו דוגמה נאה לרדוקציה עצמית, או אולי לרקורסיה ;-)). אני לא חושב שברור מההצגה שלך איך ב' עובדת ושהיא אינה נפתרת בעזרת א'. גדי אלכסנדרוביץ' - שיחה 08:43, 3 בדצמבר 2009 (IST)

טוב, מה שבטוח הוא שאין קונצנזוס על הדקויות של משמעות המושג רדוקציה. שיניתי את הניסוח בערך כך שיהיה ללא שימוש ברדוקציה.אורי מוסנזון - שיחה 14:19, 2 בדצמבר 2009 (IST)

יש קונצנזוס על משמעות המושג רדוקציה, ויש קונצנזוס על משמעות המושג רקורסיה, והשימוש במושג רדוקציה שהופיע בערך רקורסיה היה פשוט שגוי. רוזבאד - שיחה 21:04, 2 בדצמבר 2009 (IST)

הערה נוספת וחשובה, לצורך הבהרה: רדוקציה עושים אך ורק לבעיה אחרת, שיודעים שיש לה פיתרון, ויודעים מה הסיבוכיות של הפיתרון הזה. פיתרון (לבעיה המקורית) שאין לנו דרך לחשב את הסיבוכיות שלו - איננו פיתרון. ולכן, מצב שבו אנחנו עושים רדוקציה מבעיה א' לבעיה א', או עושים רדוקציה מבעיה א' לבעיה ב', כאשר בעיה ב' משתמשת בבעיה א' לצורך הפיתרון שלה - אינם קבילים כפיתרון לבעיה המקורית. רוזבאד - שיחה 23:06, 2 בדצמבר 2009 (IST)

זה לא נכון שאי אפשר לעשות רדוקציה מא' לא'. גגל Self-reducibility. פרט לכך, אני לא מבין מה זה אומר "לחשב את הסיבוכיות שלו". לא ידועה לנו כיום דרך לחשב את הסיבוכיות של בעיות NP-שלמות. גדי אלכסנדרוביץ' - שיחה 23:31, 2 בדצמבר 2009 (IST)

אני אסביר את הכוונה שלי באמצעות דוגמא: כאשר אנחנו מציעים, כפיתרון לבעיה א', לעשות רדוקציה לבעיה ב', ואנחנו יודעים או מוכיחים שהסיבוכיות של ביצוע הרדוקציה היא, למשל, לינארית, וכי הסיבוכיות של הפיתרון של בעיה ב' היא, למשל, פולינומיאלית, אז אנחנו יכולים להסיק מכך מהי הסיבוכיות של הפיתרון המוצע. רוזבאד - שיחה 23:48, 2 בדצמבר 2009 (IST)

אני מסכים עם גדי ועם אורי שרדוקציה יכולה להיות גם מקלט נתון של בעיה לקלט אחר. רדוקציה מבעיה לבעיה מסייעת לחסום סיבוכיות; רדוקציה עצמית מהסוג הזה מסייעת בחישוב הסיבוכיות של הבעיה עצמה. עוזי ו. - שיחה 23:52, 2 בדצמבר 2009 (IST)

יפה. בדוגמאות קלאסיות לרדוקציה עצמית מראים על בעיות מסויימות שאם הן פתירות ביעילות במקרה הממוצע, אז הן פתירות ביעילות (הסתברותית, כלומר BPP) במקרה הגרוע (מראים איך אפשר לבצע רדוקציה מקלט כלשהו לקלט "אקראי"). לא רדוקציה? גדי אלכסנדרוביץ' - שיחה 08:39, 3 בדצמבר 2009 (IST)

גדי, נדמה לי שרדוקציה עצמית אינה בדיוק רדוקציה של בעיה לעצמה אלא רדוקציה של בעית ההכרעה לבעית החיפוש (במסגרת אותה בעיה). תומר א. - שיחה 09:42, 3 בדצמבר 2009 (IST)

תלוי בהקשר. בדוגמה שאני נתתי (שעובדת למשל עבור RSA) יש רדוקציה של בעית החיפוש לבעית החיפוש. גדי אלכסנדרוביץ' - שיחה 10:23, 3 בדצמבר 2009 (IST)

"הדוגמא שאני נתתי" - הכוונה למשפט שמופיע שלוש תגובות מעל הנוכחית? זה אמנם מבעית חיפוש לבעיית חיפוש אבל זאת לא אותה וריאציה של הבעיה. גם דברי היו שגויים, זה לא חייב להיות מבעית הכרעה לבעיית חיפוש אבל זה לא בדיוק מבעיה לעצמה אלא מבעיה לוריאציה אחרת של אותה בעיה. תומר א. - שיחה 10:28, 3 בדצמבר 2009 (IST)

נראה לי שאתה צודק. הייתי גם מסיק מזה מסקנה כלשהי אבל אני כבר מזמן לא מבין מה בעצם מנסים לטעון בדיון הזה. גדי אלכסנדרוביץ' - שיחה 11:39, 3 בדצמבר 2009 (IST)

הדיון נפתח משום שהערך רקורסיה השתמש בצורה שגויה במושג רדוקציה. הערך שוכתב, ולמעשה הדיון הספציפי הזה תם. רוזבאד - שיחה 20:52, 3 בדצמבר 2009 (IST)

תודה

כל הכבוד על ההשקעה עזרתם לי מאוד!!!

דוגמא לא טובה

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

(מתוך הערך)

דווקא אמה של רות לא הייתה יהודיה ―79.183.241.65 (שיחה | תרומות | מונה) לא חתם ‌ 00:00, 10 בינואר 2000 (IST)

הדוגמה אינה עוסקת ברות המואבייה, אלא בסתם אישה יהודייה ששמה רות. סילקתי את השמות מהדוגמה, כדי למנוע את המשמעות שניתן לייחס להם. דוד שי - שיחה 15:02, 15 בפברואר 2019 (IST)

מיהו יהודי לפי ההלכה

בערך כתוב שע"פ ההלכה יהודי הוא מי שנולד לאם יהודיה. עם זאת, למיטב הבנתי ישנה אופציה נוספת שאותו אדם עבר תהליך גיור ויוצא כי הערך עלול להטעות קוראים בנושא, מה גם שזה תנאי עצירה מצוין לרקורסיה. אשמח להתייחסות (נגיד למקור לטענה) GonenZimm - שיחה 01:40, 17 ביולי 2019 (IDT)

אכן, גם מי שהתגייר הוא יהודי, אבל דרך זו להפוך ליהודי אינה רקורסיבית, ולכן אינה תורמת לערך שלפנינו. דוד שי - שיחה 05:43, 17 ביולי 2019 (IDT)