Рекурсивные функции. Часть 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