פונקציות רקורסיביות חלק 2

לכל פונקציה רקורסיבית יש את אותם שני חלקים:

1. מקרה הבסיס מציין מתי לעצור.
2. הצעד הרקורסיבי קורא לפונקציה עם קלט קטן יותר.

העצרת של n היא n * (n - 1) * ... * 1, לכן העצרת של n היא n כפול העצרת של n - 1:

func factorial(n: int) -> int:
	if n == 1: # מקרה בסיס
		return 1
	return n * factorial(n - 1) # צעד רקורסיבי

factorial(5) קוראת ל־factorial(4), שקוראת ל־factorial(3), וכך הלאה עד factorial(1), שמחזירה 1. בדרך חזרה, כל קריאה מבצעת כפל: התוצאה היא 120.

קלט קטן יותר לא חייב להיות מספר קטן יותר. גם מחרוזת קצרה יותר מתאימה. הפונקציה הזו הופכת מחרוזת:

func reverse_text(text: String) -> String:
	if text.length() <= 1: # מקרה בסיס
		return text
	return reverse_text(text.substr(1)) + text[0]

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

print(reverse_text("hello"))

olleh