Практика 6

Задания в классе

Тема занятия - итеративные рекурсивные функции.

В прошлый раз мы строили линейную древовидную рекурсию. В этой практике мы изучим метод оптимизации рекурсии, который уменьшает объем информации, требуемый для запоминания отложенных вычислений.

В общем случае, итеративный процесс - это такой процесс, состояния которого можно описать конечным числом переменных состояния плюс заранее заданное правило, определяющее как эти переменные состояния изменяются от шага к шагу, и плюс тест на завершение процесса.

Не смотря на то, что мы будем работать с Итерациями, но во всех заданиях запрещено использовать цикл 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$ . Тогда на каждом шаге применяем одновременную трансформацию:

a <- a + b
b <- a

Напишите линейно итеративный алгоритм для вычисления n-го числа ряда Фибоначчи.

Возведение в степень

Для закрепления изученного напишите функцию возведения числа в степень следующими способам:

Линейнорекурсивным методом
Линейноитеративным методом

Разрешено использовать только умножение, вычитание, сложение и рекурсию.

$\begin{aligned} b^n = b * b^{n-1} \\ b^0 = 1 \end{aligned}$

Домашнее задание

Циклы for и while использовать запрещено.

Быстрое возведение в степень

Существует более быстрый алгоритм возведения числа в степень, основывающийся на следующем наблюдении:

$\begin{aligned} b ^ n = {(b^{n/2})} ^ 2 && if \ n \ is \ even \\ b ^ n = b * b^{n-1} && if \ n \ is \ odd \end{aligned}$

А также примите во внимание факт, что

$(b^{n/2})^2 = (b^2) ^ {n/2}$

Реализуйте быстрое возведение в степень линейно Рекурсивным и Итеративным методом.

Разрешено использовать только умножение, вычитание, сложение и рекурсию.

Вычисление квадратного корня числа

$\sqrt{x} = y, \ where \ y \ge{0} \ and \ y^2 = x$

Использовать метод Ньютона.

Hints

Для решения задачи можно прочитать главу 1.1.7 (стр 40) из книги “Структура и интерпретация компьютерных программ”. Там используется в примерах язык Lisp, но это не должно пугать.

Напишите сами необходимый набор юнит тестов.