Шаг 60.
Основы языка Haskell. Сложные типы рекурсии на числовых структурах. Трансформация функций для приведения к простой рекурсии (окончание)

    На этом шаге мы рассмотрим еще один пример трансформации функций.

    Рассмотрим еще один пример.


    Пример 2 ([1, с.83]).

    Рассмотрим следующие рекуррентные соотношения:

   f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2).

    Преобразуем эту рекурсию высшего порядка в простую рекурсию.

    Рассмотрим новую функцию, значением которой является пара:

   g(n)=(f(n+1),f(n)),
для которой
   g(0)=(f(1),f(0))=(1,1).

    Определим рекуррентные соотношения для функции g():

   g(n+1)=(f(n+2),f(n+1))=(f(n+1)+f(n),f(n+1)) =>
         => g(n+1)=(u+v,u)
               where (u,v)=(f(n+1),f(n))=g(n).

    Остаётся преобразовать выражение для функции f():

   f(n+2)=f(n)+f(n+1) => f(n+2)=u+v
                            where (u,v)=(f(n+1),f(n))=g(n).

    Таким образом, получена взаимная рекурсия:

    Поработаем с демонстрационными примерами.

   -- Демонстрация применения трансформации программ на при-
   -- мере функции, вычисляющей n-ое число Фибоначчи с помо-
   -- щью рекуррентных соотношений:
   --
   --  f(0)=1, f(1)=1,
   --
   --  f(x)=f(x-1)+f(x-2) 
   -- *********************
   fib:: Integer -> Integer
   fib 0     = 1
   fib 1     = 1
   fib (n+1) = fib n + fib (n-1)
   -----------------------------
   -- Результат трансформации
   --------------------------
   f 0 = 1
   f 1 = 1
   f n = u+v
      where (u,v)=g (n-2)
   ----------------------
   g 0 = (1,1)
   g n = (u+v,u)
      where (u,v)=g (n-1)
   -- *************************************************
   -- Функция, возвращающая аргумент функции Фибоначчи,
   -- для которого значение функции меньше 4294967295
   -----------------------------------------------------
   len = fst $ last $ takeWhile (\(x,y) -> y<4294967295)
                                (map (\x -> (x,f x)) [1..])
   -- *****************************************************
   -- Неудачные тестовые примеры:
   ------------------------------
   test1 =   fib 11 ==     144 
          && fib 23 ==   46368
   ---------------------------
   test2 =   f 11   ==     144 
          && f 23   ==   46368
          && f 30   == 1346269
   -----------------------------
   test3 = f 3000+f 3001==f 3002
Файл с примерами можно взять здесь.
(1)Сергиевский Г.М., Волчёнков Н.Г. Функциональное и логическое программирование. - М.: Издательский центр "Академия", 2010. - 320 с.

    На следующем шаге мы рассмотрим некоторые итерационные методы решения уравнений.




Предыдущий шаг Содержание Следующий шаг