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

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