Ревизия: 226 |
Глава 5. Логические выражения, условия и рекурсия |
|
|
|
|
5
>>>
По умолчанию, максимальная глубина рекурсии равна 1000.
Упражнение. Напишите простую функцию, вызывающую саму себя, и поэкспериментируйте с изменением максимальной глубины рекурсии. Прокомментируйте свои результаты.
§5.12. Числа Фибоначчи
Леонардо Фибоначчи (Леонардо Пизанский) – крупный средневековый итальянский математик (1170-1240), автор «Книги об абаке» (1202), которая несколько веков оставалась основным сборником сведений об арифметике и алгебре. Сегодня имя Фибоначчи чаще всего упоминается в связи с числовой последовательностью, которую он обнаружил, изучая закономерности живой природы.
Ряд этих чисел образуется следующими значениями 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 и так далее – каждое последующее число ряда получается сложением двух предыдущих.
Особенностью ряда чисел Фибоначчи является то, что по мере роста номера числа в последовательности, отношение предшествующего члена к последующему приближается к значению – 0.61811 (древние греки называли это число «золотым сечением»), а последующего к предыдущему – к 1.618. «Золотым» это соотношение называют из-за того, что на нем же основан принцип музыкальной, цветовой и геометрической гармонии.
[NOTE: Про числа Фибоначчи можно много интересного написать, но я оставил это на потом]
Давайте напишем функцию, рассчитывающую n-й элемент ряда Фибоначчи. Итак, мы имеем обобщенную формулу: f 1= f 2=1, f n= f n−1 f n−2 , n { 0 } . Можем ли мы применить здесь рекурсию?
Каждое число Фибоначчи представляет собой сумму двух предыдущих чисел Фибоначчи, которые рассчитываются по той же формуле, все числа Фибоначчи целые и положительные, кроме того, мы имеем граничное значение. Так что применить рекурсию в данном случае вполне можно.
|
>>> def fibonacci(n): |
||||
|
... |
if n == 0: |
|||
|
... |
|
return 0 |
||
|
... |
if n == 1 or n == 2: |
|||
|
... |
|
return 1 |
||
|
... |
return fibonacci(n-1) + fibonacci(n-2) |
|||
|
... |
|
|
|
|
|
>>> fibonacci(7) |
||||
|
13 |
|
|
|
|
|
|
|
|
||
11 Точное значение равно |
|
−1 . |
|||
5 |
|||||
|
|
2 |
|||
59
Ревизия: 226 Глава 5. Логические выражения, условия и рекурсия
Замечательно. Теперь осталось добавить проверку типа и положительности параметра функции и готово.
def fibonacci(n):
if type(n) != type(1) or n < 0: # Проверка корректности n return None
if n == 0: return 0
if n == 1 or n == 2: return 1
return fibonacci(n-1) + fibonacci(n-2)
Упражнение. Создайте рекурсивную функцию, возвращающую сумму
n
∑i3=13 ... n3 .
i=1
60