Тема занятия - итеративные рекурсивные функции.
В прошлый раз мы строили линейную древовидную рекурсию. В этой практике мы изучим метод оптимизации рекурсии, который уменьшает объем информации, требуемый для запоминания отложенных вычислений.
В общем случае, итеративный процесс - это такой процесс, состояния которого можно описать конечным числом переменных состояния плюс заранее заданное правило, определяющее как эти переменные состояния изменяются от шага к шагу, и плюс тест на завершение процесса.
Не смотря на то, что мы будем работать с Итерациями, но во всех заданиях запрещено использовать цикл for и while.
В прошлый раз мы рассматривали обычное рекурсивное определение факториала:
$$ n!= \begin{cases} 1 & n = 0,\\ n \cdot (n-1)! & n > 0. \end{cases} $$
Очевидно, что его можно переписать в итеративной форме:
$$ n! = 1\cdot 2\cdot\ldots\cdot n =\prod_{k=1}^n k $$
Из определения мы можем заметить что:
произведение = счетчик * произведение
счетчик = счетчик + 1
Тогда
def factorial(n):
return fact_iter(1, 1, n)
def fact_iter(product, counter, max_count):
if counter > max_count:
return product
return fact_iter(counter * product, counter + 1, max_count)
Нарисуйте на доске процесс вычисления факториала. В этот раз у нас получился линейно итеративный процесс.
Математическое рекурсивное определение при переносе в программу даёт очень неэффективный алгоритм.
$$ F = \begin{cases} F(0)=1; \\ F(1) = 1; \\ F(n) = F(n-1) + F(n-2),\quad n > 1. \end{cases} $$
Идея: будем использовать две переменные a и b,
которые в начале процесса зафиксируем значениями $Fib(1) = 1$ и $Fib(0) = 0$.
Тогда на каждом шаге применяем одновременную трансформацию:
$$ \begin{aligned} a \leftarrow a + b \\ b \leftarrow a \end{aligned} $$