Некоторые простые функции: рекурсия
Еще одна вещь, которую мы хотим показать Вам, чтобы сделать все завершенным, - это рекурсия.
Этот термин может описывать множество различных концепций, но особенно интересна одна из них - относящаяся к компьютерному программированию.
В этой области рекурсия - это метод, при котором функция вызывает сама себя.
Эти два случая, кажется, лучше всего иллюстрируют этот феномен - факториалы и числа Фибоначчи. Особенно последний.
Определение чисел Фибоначчи - наглядный пример рекурсии. Мы уже говорили Вам, что:
Fibi = Fibi-1 + Fibi-2
Определение i-го числа привязано к i-1 числу и так далее, пока вы не дойдете до первых двух.
Можно ли это использовать в коде? Да, можно. Это также может сделать код короче и понятнее.
Вторая версия нашей функции fib() напрямую использует это определение:
def fib(n):
if n < 1:
return None
if n < 3:
return 1
return fib(n - 1) + fib(n - 2)
Теперь код стал намного понятнее.
Но так ли это безопасно? Влечет ли это за собой риск?
Да, риск действительно есть. Если Вы забудете учесть условия, которые могут остановить цепочку рекурсивных вызовов, программа может войти в бесконечный цикл. Вы должны быть осторожны.
Факториал также имеет вторую, рекурсивную сторону. Смотрите:
n! = 1 × 2 × 3 × ... × n-1 × n
Очевидно, что:
1 × 2 × 3 × ... × n-1 = (n-1)!
Итак, наконец, результат:
n! = (n-1)! × n
По сути, это готовое описание нашего нового решения.
Вот оно:
def factorial_function(n):
if n < 0:
return None
if n < 2:
return 1
return n * factorial_function(n - 1)
Работает ли это? Да. Попробуйте сами.
Наш короткий функциональный путь почти завершен. В следующем разделе мы рассмотрим два любопытных типа данных Python: кортежи и словари.
Code
def fib(n):if n < 1:
return None
if n < 3:
return 1
elem_1 = elem_2 = 1
the_sum = 0
for i in range(3, n + 1):
the_sum = elem_1 + elem_2
elem_1, elem_2 = elem_2, the_sum
return the_sum
for n in range(1, 10):
print(n, "->", fib(n))