§5.11. Максимальная глубина рекурсии

Мы уже сталкивались с бесконечной рекурсией, когда рекурсивная функция по тем или иным причинам не достигала условия возврата (в англоязычной литературе base case -«базовый случай»). Но в большинстве программных сред такие программы, конечно же, бесконечно выполняться не будут в силу конечного размера памяти компьютера. В Питоне для предотвращения нарушений работы компьютера, на котором выполняется программа, тоже имеется специальное ограничение - maximum recursion depth {максимальная глубина рекурсии).

Максимальную глубину рекурсии можно изменять, т.к. некоторые задачи требуют большего максимального размера стека вызовов. Для этого в модуле sys имеется две функции: sys .getrecursionlimit (), возвращающая текущую максимальную глубину рекурсии и sys . setrecursionlimit (), изменяющая ее значение.

>»	import sys
>»	sys	.getrecursionl	imit()
юос
>»	sys	.setrecursionl	imit(5)
>»	sys	.getrecursionl	imit()
5
>»

По умолчанию, максимальная глубина рекурсии равна 1000.

Упражнение. Напишите простую функцию, вызывающую саму себя, и поэксперименти­руйте с изменением максимальной глубины рекурсии. Прокомментируйте свои результаты.

§5.12. Числа Фибоначчи

Леонардо Фибоначчи (Леонардо Пизанский) - крупный средневековый итальянский математик (1170-1240), автор «Книги об абаке» (1202), которая несколько веков оставалась основным сборником сведений об арифметике и алгебре. Сегодня имя Фибоначчи чаще всего упоминается в связи с числовой последовательностью, которую он обнаружил, изучая закономерности живой природы.

Ряд этих чисел образуется следующими значениями 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 и так далее - каждое последующее число ряда получается сложением двух предыдущих.

Особенностью ряда чисел Фибоначчи является то, что по мере роста номера числа в последовательности, отношение предшествующего члена к последующему приближается к значению - 0.618 (древние греки называли это число «золотым сечением»), а последующего к предыдущему- к 1.618. «Золотым» это соотношение называют из-за того, что на нем же основан принцип музыкальной, цветовой и геометрической гармонии.

[NOTE: Про числа Фибоначчи можно много интересного написать, но я оставил это на потом.]

Давайте напишем функцию, рассчитывающую n-й элемент ряда Фибоначчи. Итак, мы

имеем обобщенную формулу: /i⁼/2 ⁼ l> fn ⁼ fn-i~^~fn-2> ^we'N . Можем ли мы применить

здесь рекурсию?

62

Ревизия: 170

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

Каждое число Фибоначчи представляет собой сумму двух предыдущих чисел Фибоначчи, которые расчитываются по той же формуле, все числа Фибоначчи целые и положительные, кроме того, мы имеем граничное значение. Так что применить рекурсию в данном случае вполне можно.

>» def fibonacci (n) :
... if n == 1 or n == 2:
... return 1
... return fibonacci(n-1)	+ fibonacci(n-2)
>» fibonacci (5)
13

Замечательно. Теперь осталось добавить проверку типа и положительности параметра функции и готово.

def fibonacci(n):
if type(n) != type(l)	or n < 0:	# Проверка	корректности n
return None
if n == 1 or n == 2:
return 1
return fibonacci(n-1)	+ fibonacci	(n-2)

Упражнение. Создайте рекурсивную функцию, возвращающую сумму 2^ *' п

63

Ревизия: 170

Циклы