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

ממליץ על המאמר הבא:
http://net.nana10.co.il/Article/?Ar...ypeID=1&sid=127

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

הגלריה שלי בפליקר

עריכה: תשכחו מההודעה הזאת


לא יכלו להדגיש קצת את השורה הבאה:

ציטוט:

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

?!?!?!

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


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



----------------------------------------------------


קראתי את המאמר הזה ואני לא מצליח להבין את הלוח-פיקסלים הזה.
(לא ניסיתי פיזית להדפיס ולצבוע חחח)

נניח שהגענו למשבצת הלבנה השניה מימין, בשורה השניה מלמטה.

האם הפיקסל אינו אדום ואינו שחור? - כן

• צבענו אותו באדום
• שורה 2 מלמטה, תא 3 מימין - שחור.
• שורה 2 מלמטה, תא 1 מימין - שחור.
• שורה 3 מלמטה, תא 2 מימין - לבן. (צובע, ובודק מסביבו...)
• שורה 1 מלמטה, תא 2 מימין - שחור.

(חוץ מזה, כל שורה 2 מלמטה, שחורה).


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



מה פיספסתי?


(שונא רקורסיות )

ההודעה נכתבה לפני שראיתי שערכת...
============================

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

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

הנה דוגמא:

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

הגלריה שלי בפליקר

תודה שהשקעת בהסבר


יש לך עוד עמודים או מדריכים טובים לנושא הזה?
אני מבין איך זה עובד ולמה זה אמור לשמש, אבל ממש לא מצליח ליישם את זה בעצמי =\

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

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

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

באק טראקינג?

לפתור מבוך, למשל.

אני הבנתי רקורסיה בעזרת מיון איחוד (Merge sort )

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

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

או בפסודו קוד:

קוד PHP:

 function Array MergeSort(Array A)
  A1 = A.SubArray(0, A.Length / 2);
  A2 = A.SubArray(A.Length / 2, A.Length);

  return Merge(MergeSort(A1),MergeSort(A2));


function Array Merge(Array A, Array B)
  int AIndex = 0;
  int BIndex = 0
  Vector result = new Vector();

  if (A[AIndex] > B[BIndex])
    result.push_back(A[AIndex++]);
  else
    result.push_back(B[BIndex++]);

// Obviously one could be longer then the other and you need to handle that too....
 
  return result.ToArray(); 


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

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

המאמר מנענע לא עזר לך?

הגלריה שלי בפליקר

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

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

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

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

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

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

ככה אני הבנתי את זה, בכל מקרה...

בברכה, מתן.
www.MatanNarkiss.com

רקורסיה, זה עץ, לולאה, זה לינארי

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

בברכה, מתן.
www.MatanNarkiss.com

הבנתי את האנלוגיה.

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

להתייחס לרקורסיה כאל לולאה?
תאמת הקשר מקרי בהחלט.. רקורסיה היא כמו אינדוקציה מתמטית.

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

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

שימוש ברקורסיה סתם לצורך לולאה, זה שימוש בזבזני במשאבים ומיותר.

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

קוד:

f(n) = f(n − 1) + f(n − 2)

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

1) טענה מאוד מעניינת..(לגבי פיבנאצי).



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

דוגמה קלאסית היא תשובה לשאלה האם המערך(של ממשיים\שלמים) כולל איברים שסכומם הכולל בדיוק K



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

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




2)אכן יש שפות כאלה, אבל להגיד שהן נועלות זה קצת מוזר..

ציטוט:

חוץ מזה שקומפיילר נורמלי אמור לדעת לזהות רקורסיות שהן איטרטיביות מטבען (ראש-זנב) ולהמירן ללולאות.

אם אתה אומר.. אני לא מכיר את הנושא.

1. חוכמולוג שורש 5.... גם כן מספר....

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

אתה יודע איך נראה קוד של מיון מיזוג בC ?
ככה הוא נראה בשפה פונקציונאלית

קוד PHP:

 (defun merge-sort (list)
  (if (small list) list
      (merge-lists
        (merge-sort (left-half list))
        (merge-sort (right-half list))))) 


אתה צריך עוד את Small

קוד PHP:

 (defun small (list)
  (or (null list) (null (cdr list)))) 


ואת המיזוג

קוד PHP:

 (defun merge-lists (list1 list2)
  (merge 'list list1 list2 #'<)) 


וזה חוצה רשימות לשניים

קוד PHP:

 (defun right-half (list)
  (last list (ceiling (/ (length list) 2))))
(defun left-half (list)
  (ldiff list (right-half list))) 


1 הדרך שלך להתבטא דוגלת בטיפשות. מה זה "חוכמולוג"?
(1\2)^5 הוא אכן מספר לכל דבר. זה מאוד טיפשי מצדך לתת את ההערה הזו, לא מדובר כאן באיזה משהו מעורך, אלה בשיווין של ממש, ואכן אפשר להוכיח בנקל, כי הטווח של פונקציה זו, הוא המספרים הטבעים. במקרים שבהם מציאת נוסחה ישירה זה אפשרי, הדבר עדיף אלפי מונים על נוסחת נסיגה, והופך את הפתרון לO(1)
בעוד שנוסחה רקורסיבית של פיבונאצי שממומשת לא בצורה טובה(בלי ממוריזישן, זה אסון של ממש).
אבל גם הממוש הטוב ביותר לא יהיה קרוב ליעילות של נוסחה ישירה.

2

ציטוט:

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

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

קוד PHP:

 public static void merge(int[] arr,int i, int j){
        int[] tmp_arr = new int[j-i+1];
        int sl=i,sr=(i+j)/2+1;
        int k=0;
        
        while ((sl<=(i+j)/2) && (sr<=j)){
            if (arr[sl]<arr[sr]){
                tmp_arr[k]=arr[sl];sl++;
            }
            else{
                tmp_arr[k]=arr[sr];sr++;
            }
            k++;
            
        }
        
        while (sl<=(i+j)/2){
            tmp_arr[k]=arr[sl];sl++;k++;
        }
        
            while (sr<=j){
            tmp_arr[k]=arr[sr];sr++;k++;
        }
        
        k=0;
        for(;i<=j;i++,k++){
            arr[i]=tmp_arr[k];
        }
    }
    
    public static void sort(int[] arr,int i,int j){
    
        if (i==j) return;//nothing to sort, only one item..
        
        sort(arr,i,(i+j)/2);
        sort(arr,(i+j)/2+1,j);
        merge(arr,i,j);
    } 


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

1. היה בהומור.

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

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

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

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

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

שמע גם הקצאות על המחסנית זה לא חינם.
אל זה לא היה העיניין, אלא הפשטות של LISP מול C

זה הקוד בC

קוד PHP:

 void mergeSort(int numbers[], int temp[], int array_size)
{
  m_sort(numbers, temp, 0, array_size - 1);
}
 
 
void m_sort(int numbers[], int temp[], int left, int right)
{
  int mid;
 
  if (right > left)
  {
    mid = (right + left) / 2;
    m_sort(numbers, temp, left, mid);
    m_sort(numbers, temp, mid+1, right);
 
    merge(numbers, temp, left, mid+1, right);
  }
}
 
void merge(int numbers[], int temp[], int left, int mid, int right)
{
  int i, left_end, num_elements, tmp_pos;
 
  left_end = mid - 1;
  tmp_pos = left;
  num_elements = right - left + 1;
 
  while ((left <= left_end) && (mid <= right))
  {
    if (numbers[left] <= numbers[mid])
    {
      temp[tmp_pos] = numbers[left];
      tmp_pos = tmp_pos + 1;
      left = left +1;
    }
    else
    {
      temp[tmp_pos] = numbers[mid];
      tmp_pos = tmp_pos + 1;
      mid = mid + 1;
    }
  }
 
  while (left <= left_end)
  {
    temp[tmp_pos] = numbers[left];
    left = left + 1;
    tmp_pos = tmp_pos + 1;
  }
  while (mid <= right)
  {
    temp[tmp_pos] = numbers[mid];
    mid = mid + 1;
    tmp_pos = tmp_pos + 1;
  }
 
  for (i=0; i <= num_elements; i++)
  {
    numbers[right] = temp[right];
    right = right - 1;
  }
} 


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

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

בברכה, מתן.
www.MatanNarkiss.com

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

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

בברכה, מתן.
www.MatanNarkiss.com

אני רוצה לצטט איזה קטע מהכתבה בננע(אותה הכתבה שנתנו כאן בתחילת האשכול).

ציטוט:

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

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

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

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

בברכה, מתן.
www.MatanNarkiss.com

הם צודקים.
מצביעים זה מטומטם.

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

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

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

קוד PHP:

 int x = 5;
int *y;
y = &x;
printf ("%d", *y); 


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

בברכה, מתן.
www.MatanNarkiss.com

איזה שפות תכנות אתה מכיר?
ולמיטב זכרוני אתה סטודנט למדמ"ח?

הנדסת תוכנה - סיים שיט.
מה אני מכיר? מהלימודים יצא לי לכתוב קצת ב ++C, C, ג'אווה ואסמבלי (8086 ו MANO) ועכשיו אני לומד בעצמי את פה"פ.
היתה לנו הכירות בקורס "שפות תכנות" עם שפות כמו ML, ועמדנו על התיאוריה שמאחורי שפות פונקציונליות, פרוצדורליות וכל מיני דברים כאלה, אך אם לומר את האמת, זה לא החלק שבאמת מעניין אותי

בברכה, מתן.
www.MatanNarkiss.com

יום אחד כשיהיה לך משעמם תקרא את שני אלה:
http://www.defmacro.org/ramblings/fp.html
http://www.defmacro.org/ramblings/lisp.html

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

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

מה קשור מה שאני כתבתי, למה שאתה כתבת?

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

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

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

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

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

אתה טועה. וC זה ממש לא הבסיס הבסיס זה ALGOL ו LISP, בהצלחה עם הראשון, השניה בגרסתו המודרנית דיי שונה מגרסתו משנות ה50.

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

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

ממש, אבל ממש לא.

ממש אבל ממש לא זו דעתך.
ממש אבל ממש כן זו דעתי.

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

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

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

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

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

בברכה, מתן.
www.MatanNarkiss.com

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

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


יש את ההזויים מצד אחד שחושבים שאם הם ילמדו תחביר של 14 שפות תכנות הם יהיו מתכנתים, ויש את ההזויים מהצד השני שחושבים שכדי להיות מתכנת צריך לדעת הכל חוץ מתכנות...

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

+1

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

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

בברכה, מתן.
www.MatanNarkiss.com

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

חברי כנסת ישרים

אני חושב שהוא מתכוון לג'אווה

בברכה, מתן.
www.MatanNarkiss.com

בג'אווה יש באגים נוראיים, והכי נורא זה שבגלל תאימות הוסיפו לדוטנט את הבאגים האלה.

"זה לא באג, זה פיצ'ר!"

בברכה, מתן.
www.MatanNarkiss.com

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

אני לא סובל ג'אווה. זה כמו האחות הגדולה והחולה נפשית של C#

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

אם בא לך להגיב קצת עיניינית אני אשמח. ואני בטוח שכולם

שתי משמעויות לרקורסיה

בדיון למעלה נעשה בלבול בין שני דברים שונים.

משמעות אחת למושג רקורסיה, היא במובן של הגדרה רקורסיבית, כמו לדוגמה, הגדרה רקורסיבית
לסדרת פיבונא'צי⁽¹⁾ או הגדרה רקורסיבית של עצרת על המספרים הטבעיים⁽²⁾ - שתיים מהדוגמות
הנפוצות ביותר. דוגמה אחרת היא המשוואה הלוגיסטית⁽³⁾ (או 'המפה הלוגיסטית') - נוסחה שמייצגת
מודל פשוט מאוד לגידול של אוכלוסיה בבית-גידול נתון (r הוא "מקדם הגידול").

[tex]\begin{align}(1) \quad & F_1 = F_2 = 1 \\ \ & F_{n+1} = F_n+F_{n-1} \\ (2) \quad & N! = 0 \\ \ & N! = (N-1)! \cdot N \\ (3) \quad & X_{n+1} = r X_n (1-X_n) \end{align}[/tex]

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

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


רקורסיה ולולאות

אין הבדל בין רקורסיה ללולאות.

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

באופן דומה, בשפה מסוימת יכול להיות שרקורסיה ולולאה נראות שונה, אבל מנגנון הקריאה לפונקציות
הוא בסופו של דבר רק לדחיפת נתונים למחסנית וביצוע JMP, ובמקרה של פונקציות רקורסיביות -
דחיפת מידע למחסנית וביצוע JMP לתחילת ה"פונקציה" או ה"לולאה" (וגם לזה יש syntactic sugar
אפילו באסמבלי של x86 - ההוראה LOOP)

אין כאן אנלוגיה מוזרה, ואין כאן עצים ולינאריות. זה בדיוק אותו דבר.

לולאה לחלוטין איננה "פעולה אחת לינארית שחוזרת על עצמה". כמובן שזה תלוי בדרך שבה אנחנו
מגדירים "פעולה אחת לינארית" (אפשר להכניס כל פונקציה ב-C לתוך do { ... } while (0);‎, כדוגמה
קיצונית), אבל הלולאה שבתוך printf/scanf נראית קצת מוזר, והלולאה שבתוך NetPathCanonicalize
זה בכלל משהו הזוי. תציץ בה.

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

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

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

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

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

קוד:

(defun fibonacci (n)
  (if (< n 2) 
    n
    (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))

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

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

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

זה לא שההגדרה שלי לא נכונה, היא נכונה - אבל לא 100% מדוייקת.
בסוף כל התפצלות יהיה תנאי עצירה (כשנגיע לעלה בעץ), אבל ההתפצלות לא חייבת להיות שירשור של עץ עם בן אחד לכל צומת. בהחלט יתכן כי ההתפצלות תייצר עוד בנים (למשל סריקת עץ ע"י in-order) ואז באמת יהיו כמה קריאות ריקורסיביות מכל צומת.
בכל מקרה, אני נהניתי מהאשכול הזה. מדהים איך בכל פעם מחדש משווים שפות תכנות וקובעים אילו שפות הן יותר טובות ופחות טובות, אפילו שהשאלה לא היתה תלויית שפה בעליל ^_^

בברכה, מתן.
www.MatanNarkiss.com