Тема занятия - рекурсивные функции. Поэтому во всех заданиях запрещено использовать цикл for и while.
<aside> 🤔 Человеку свойственна итерация, рекурсия – удел богов. (James O. Coplien, Bell Labs)
</aside>
$$ n!= \begin{cases} 1 & n = 0,\\ n \cdot (n-1)! & n > 0. \end{cases} $$
Если в лоб записать определение факториала на python, то получится линейно рекурсивная функция.
def factorial(n):
if n == 0:
return 1
return n * factorial(n-1)
print(factorial(10) == 3628800)
Нарисуйте на доске процесс вычисления факториала. У вас должна получиться серия расширений, а потом сжатий отложенных операций.
Этот процесс расширения и сжатия называется рекурсивным процессом. В случае с факториалом мы имеем дело с линейнорекурсивным процессом, так как объем информации, требуемый для запоминания отложенных операций растет линейно.
Этот вид рекурсии называется древовидным. Нарисуйте процесс порождаемый при вычислении F(5) и вы увидите, что он напоминает дерево. Как вы думаете на сколько это оптимальный процесс?
$$ F = \begin{cases} F(0)=1; \\ F(1) = 1; \\ F(n) = F(n-1) + F(n-2),\quad n > 1. \end{cases} $$
Поиск максимального элемента в коллекции
maximum(1, 3, 2, 6, 5, 1) == 6
Сумма цифр числа рекурсивным методом.
summa(1234) == 1 + 2 + 3 + 4 == 10