Рекурсивные функции. Часть 1

Рекурсивная функция — это функция, которая вызывает саму себя. Каждый вызов решает меньшую версию задачи, пока задача не станет достаточно простой, чтобы решить её напрямую.

Эта функция складывает все целые числа от 1 до n:

func sum_to_n(n: int) -> int:
	if n == 0: # базовый случай
		return 0
	return n + sum_to_n(n - 1) # рекурсивный шаг

Он состоит из двух частей:

• Базовый случай даёт ответ, не вызывая функцию снова: сумма до 0 равна 0.
• Рекурсивный шаг вызывает функцию с меньшим значением, n - 1, и строит ответ на основе результата.

sum_to_n(3) — это 3 + sum_to_n(2), то есть 3 + 2 + sum_to_n(1), то есть 3 + 2 + 1 + sum_to_n(0). Базовый случай возвращает 0, а ожидающие вызовы завершаются один за другим: результат — 6.

Каждый рекурсивный шаг должен приближать к базовому случаю. Без базового случая или при шаге вроде n + 1, который никогда его не достигает, функция продолжает вызывать саму себя. Godot допускает около 1 000 вложенных вызовов, а затем останавливает программу с ошибкой.