06-08-2005, 21:22
|
|
|
חבר מתאריך: 20.12.01
הודעות: 20,962
|
|
ריקורסיה היא הגדרת פונקציה דרך אותה פונקציה עצמה.
לדוגמה: ההגדרה של פעולת העצרת("עצרת-N") היא N כפול העצרת של המספר
הקטן באחד מ-N, כלומר N*עצרת(N-1). פה הגדרנו את המשמעות של פעולת
העצרת ע"י פעולת העצרת עצמה.
בכל ריקורסיה מועילה חייבים להיות תנאי עצירה או תנאי קצה. במקרה על עצרת
מוגדר כי עצרת(1)=1, לכן אם נרצה לחשב את העצרת של 5, נחשב 5*עצרת-4.
עצרת-4 שווה ל-4*עצרת-3 וכך הלאה:
5! = 5*4! = 5*4*3! = 5*4*3*2! = 5*4*3*2*1! = 5*4*3*2*1 = 120
אם תרצה לתרגם את זה ל-C, זה יראה בערך כך:
קוד PHP:
int factorial(int N) { if ((N==1)||(N==0)) { return 1; } else { return (N*factorial(N-1)); } }
הוספתי את הכלל שאומר שעצרת של 0 היא גם 1. שים לב שישנו פגם
בפונקציה: היא תפעל בצורה שגויה עבור מספרים שליליים, והשימוש
שלה ב-int עבור מכפלת של int-ים רבים עלול לגרום לשגיאת גלישה.
אבל אלה הן בעיות טכניות ולא משהו עקרוני לעניין הריקורסיה. את הבעיה
הראשונה, נפתור כך לדוגמה:
קוד PHP:
int factorial(int N) { if ((N==1)||(N==0)) { return 1; } else if (N<0) { return (-1); } else { return (N*factorial(N-1)); } }
אם הפרמטר שמקבלת הפונקציה הוא מספר שלילי, הפונקציה מחזירה
(-1), שבמקרה שלנו מוגדר כקוד שגיאה עבור פרמטר שלילי. (שים לב
שזה אפשרי רק כי הערך המוחזר של העצרת חייב להיות חיובי, ולכן ניתן
להשתמש בערכים שליליים כקודי שגיאה)
|