רקורסיה חומר עזר C++

[brokenn]

רקורסיה חומר עזר C++

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

 

[nocgod]

דווקא בעברית?

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

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

 

[brokenn]

באופן כללי

אני לא כל כך מבינה את הנושא,איך לכתוב את הפונקציה וכו'-מהבסיס

 

[Desslok of Gamilon]

היה פה הסבר ממש לא רע בשאלות הנפוצות אבל העימוד קצת התחרבש כשתפוז שינו את מערכת הפורומים. הנה כאן:
http://www.tapuz.co.il/forums2008/faq/Question.aspx?forumid=89&qId=15890

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

 

[nocgod]

well

כתובים פונקציה רקורסיבית כמו כל פונקציה אחרת
<type> <name>(<param list>)
{
// body
<return if type is not void>
}


רק שבתוך גוף הפונקציה צריך להיות זימון של הפונקציה לעצמה (במקרה הפשוט)

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

 

[nocgod]

כמה דוגמאות לפונקציות פשוטות

#include <iostream>
using std::cout;
using std::endl;

int factorial(int n)
{
return n * factorial(n - 1);
}

double power(double base, int exp)
{
if (exp == 1)
{
return base;
}
else
{
return base * pow(base, exp-1);
}
}

double newton_raphson(double n, double guess, int degree, int* count)
{
if ( abs(power(guess,degree) - n) > 0.000001)
{
(*count)++;
return newton_raphson( n, guess - (power(guess,degree) - n) / ( degree * power(guess,degree-1) ), degree, count);
}

return guess;
}

double newton_raphson(double n, int degree, int* count)
{
return newton_raphson(n, ((int)n)/degree, degree, count);
}

int fibonacci(int n)
{
if (n == 1 || n == 0)
{
return n;
}
else
{
return fibonacci(n - 1) + fibonacci(n - 2);
}
}

int gcd(int a, int b)
{
if (b == 0)
{
return a;
}
else
{
return gcd(b, a % b);
}
}

int main()
{
int count = 0;
double number = 123123123;
int base = 29;
printf("Newton-Raphson: root of %f in degree %d:\n%0.8f\n", number, base, newton_raphson(12323123, 29, &count));
printf("There were %d recursive calls to the function.\n", count);

//cout << gcd(1122,867) << endl;
return 0;
}


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

הסבר קצר על הפונקציה ניוטון רפסון שכתבתי: בכללי ניוטון-רפסון הוא אלגוריתם אנליזה נומרית רקורסיבי למציאה של שורשים של פונקציות, במקרה שלי מציאה של שורש של מספר (n - x^i).
הפרמטרים שאני מעביר לפונקציה (הקצרה יותר, הארוכה יותר היא "לשימוש פנימי" נגיד ככה) הם: המספר, הניחוש ההתחלתי לשורש (אני מנחש מספר חלקי דרגת שורש), דרגת שורש, ומצביע למונה אשר מונה כמה פעמים
נכנסים לפונקציה רקורסיבית. הmain מריץ דוגמא לnewton-raphson...

אם משהו לא מובן, את יכולה בכיף לשאול פה או בפרטי...

 

[brokenn]

תודה רבה לכולם!!!!