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

סוגים:
1. ניתן לפרק בעיה גדולה לבעיות קטנות.
למשל

5!=5*4!

4!=4*3!

3!=3*2!

2!=2*1!

1!=1 =======> תנאי העצירה

2. נוסחת כלל נסיגה:

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

a(n)=a(n-2)+a(n-1)

a(n-2)=a(n-4)+a(n-3)

a(n-1) = a(n-3)+a(n-2)

…..

a(1)=1 ======> תנאי העצירה

a(2)=1======> תנאי העצירה

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