§5.9. Рекурсия

Разобравшись с логическими операциями и условным оператором, перейдем к изучению очень мощной концепции, которая называется рекурсией. Для того, чтобы лучше понять, где она применяется, рассмотрим задачу, которая сама приведет нас к ней.

Помимо привычных нам арифметических в математике есть и другие операции. В

частности, факториал: например, 3/=1 *2 *3 —б⁹. В общем виде п! — \ *...*п, где

weNu(O) ¹⁰, причем 0/ = 1 .

Растут значения факториала очень быстро, например 5/ = 120, 7/ = 5040, а

10 / = 3628800 . Поэтому логично было бы поручить вычисление факториалов компьютеру.

Прежде чем приступать к реализации функции факториала давайте проанализируем формулу, по которой она вычисляется. При условии, что мы не знаем чему равно число п

применить формулу п!—\ *...*п «в лоб» не получится. Поэтому давай-те ее

проанализируем:

п!=1*2*...*п,

(п+1)!= 1*2*...*п*(п+1)=п!*(п+1), иначе говоря:

п! = (п—\)!*п

Это уже что-то. По сути, зная значение [п— 1) /, мы можем вычислить п! всего за одну

операцию. Аналогично, {п— 1)! = (п — 2)!*{п— 1) . Попробуем реализовать эту идею на

Питоне. Мы уже говорили о том, что из тела одной функции можно вызывать другую функцию. Почему бы не попробовать вызвать из функции эту же самую функцию? Это как раз то, что нам надо, давайте попробуем:

>» def

fact(n):

return fact(n-

D*

n

>» fac

t(3)

File

"<stdin>",

line

2,

in

fac

t

[...]

File

"<stdin>",

line

2,

in

fac

t

Runtime

Error: maximum

recursion

depth

excee

de

d

Хм, вызывать функцию из самой себя, видимо, можно, но интерпретатор вывел длинный список обратной трассировки и сообщение об исключении: RuntimeError: maximum recursion depth exceeded- «Достигнута максимальная глубина рекурсии». Вот и упоминание рекурсии. Сформулируем определение - возможно, это нам поможет в поиске решения проблемы.

Рекурсивными функциями являются функции, получаемые в результате конечного числа применений самих себя для целочисленных значений аргумента (параметра). Важно

3. Читается как «три факториал».

4. Число п принадлежит множеству натуральных чисел, объединенному с нулем, иначе говоря, может быть равным 0, 1, 2, 3 и т.д.

59

Ревизия: 170

Логические выражения, условия и рекурсия

заметить то, что такие функции применимы лишь к целочисленным значениям, но не к дробным.

Мы передали целочисленный аргумент- 3, но возникло исключение. Видимо, мы имеем дело с семантической ошибкой: программа делает не то, что мы подразумевали. Давайте попробуем повторить выполнение нашей программы в уме.

Итак, вызов funct (3) должен вернуть funct (2) *3, далее funct (2) - это все равно что funct (1)*2; затем идет вызов funct (0), потом funct (-1). Но п- должно быть натуральным числом или нолем! Получается, что, дойдя до граничного значения области допустимых значений п, наша программа продолжает выполнять вызов функции funct () как ни в чем ни бывало, и даже не думает останавливаться. Более того, программа «не знает» чему равен 0! - мы забыли это указать, но все поправимо.

>»	def fact(n) if n ==	0:
. . .	ret	urn	1
	return	f ac	t (n-	-1)	*n
>»	fact(3)
6

Работает! Осталось только проверить, как функция поведет себя при некорректных значениях параметра (отрицательных или дробных, например), так что не забудьте выполнить упражнение.

Упражнение. Проверьте, как функция fact () будет вести себя с отрицательными и дробными значениями параметра. Объясните, какие проблемы возникли и почему. Модифицируйте функцию так, чтобы избежать их¹¹.