Шаг 56.
Основы языка Haskell.
Сложные типы рекурсии на числовых структурах. Параллельная рекурсия

    На этом шаге мы рассмотрим этот вид рекурсии.

    К сложным типам рекурсии относятся:

Параллельная рекурсия

Определение.
Параллельной рекурсией (рекурсией CAR-CDR, рекурсией по дереву) называется рекурсия, встречающаяся одновременно в нескольких аргументах функции.


   Замечание. Название параллельной рекурсии "рекурсией по дереву" связано с тем, что её часто приходится использовать для обхода  древовидных структур данных, т.е. списка, элементами которого являются списки.

    Приведем примеры такой рекурсии.

   -- Демонстрация использования параллельной рекурсии на
   -- примере функции, вычисляющей n-ое число Фибоначчи с
   -- помощью рекуррентного соотношения:
   --
   --  f(0)=1, f(1)=1, f(x)=f(x-1)+f(x-2), x=2,3,... 
   -------------------------------------------------
   fibb:: Integer -> Integer
   fibb 0     = 1
   fibb 1     = 1
   fibb (n+1) = fibb n + fibb (n-1)
   --------------------------------
   fibb':: Integer -> Integer
   fibb' n | n==0 = 1
           | n==1 = 1
           | True = fibb' (n-1) + fibb' (n-2)
   ------------------------------------------
   fibb'':: Integer -> Integer
   fibb'' n 
      | n==0 = 1                        
      | n==1 = 1                        
      | True = if even n
                 then fibb'' t * fibb'' (t-1) +
                      2 * fibb'' (t-1) * fibb'' (t-1) + (-1)^t
                 else 2 * fibb'' s * fibb'' (s+1) -
                      fibb'' s * fibb'' s
      where t = n `div` 2
            s = (n-1) `div` 2
   -- ***************************
   -- Неудачные тестовые примеры:
   ----------------------------------------
   test1 = fibb  11==144 && fibb  23==46368
   test2 = fibb' 11==144 && fibb' 23==46368
   test3 = fibb  30==fibb' 30
   test4 = fibb'' 11==144 && fibb'' 23==46368
   test5 = fibb'' 11==144 && fibb'' 23==46368
   test6 = fibb'' 130 + fibb'' 131==fibb'' 132
Файл с примерами можно взять здесь.
   -- Демонстрация использования параллельной рекурсии
   -- ************************************************
   -- Функция, возвращающая число сочетаний из  n эле-
   -- ментов по m с помощью рекуррентного соотношения
   --
   --   m  m    m-1   0
   --  C =C   +C   , C =1
   --   n  n-1  n-1   n
   --
   --------------------------------
   c:: Integer -> Integer-> Integer
   c n m | n<m || n<0 || m<0 = error "n>m & n,m>0"
         | n==m || m==0      = 1
         | True              = c (n-1) m + c (n-1) (m-1)
   -----------------------------------------------------
   choose n 0 = 1
   choose n k
         | n<k  = 0
         | n==k = 1
         | True = choose (n-1) (k-1) + choose (n-1) k
   -- *************************************************
   -- Функция (эффективная), возвращающая число сочета-
   -- ний из n элементов по m с  помощью  рекуррентного
   -- соотношения
   --
   --   m  n    m-1   0
   --  C = - * C   , C =1
   --   n  m    n-1   n
   ----------------------
   binom n 0 = 1
   binom n m | n<m  = 0
             | True = (n * binom (n-1) (m-1)) `div` m
   -- ***********************************************
   -- Неудачные тестовые примеры:
   ------------------------------
   test1 =   c 64  2 == 2016
          && c  5  3 ==   10
          && c 13  5 == 1287
          && c  4  3 ==    4
          && c  4  2 ==    6
          && c 99 98 ==   99
   ------------------------------
   test2 =   choose 64  2 == 2016 
          && choose  5  3 ==   10 
          && choose 13  5 == 1287 
          && choose  4  3 ==    4 
          && choose  4  2 ==    6 
          && choose 99 98 ==   99 
   ------------------------------
   test3 =   binom 64  2 == 2016 
          && binom  5  3 ==   10 
          && binom 13  5 == 1287 
          && binom  4  3 ==    4 
          && binom  4  2 ==    6 
          && binom 99 98 ==   99 
   -----------------------------
   test4 n m = binom n m
   ---------------------------------------------
   -- Тестирование выполнения закона Ньютона для
   -- биномиальных коэффициентов
   --------------------------------------
   test5 n m k = binom n m * binom m k == 
                 binom n k * binom (n-k) (m-k)
Файл с примерами можно взять здесь.
   -- Демонстрация параллельной рекурсии на примере
   -- вычисления значения функции вида:
   --  
   --  f(0)=13, f(1)=17, f(2)=20, f(3)=30,
   --
   --  f(2n)=43*f(n)+57*f(n+1),
   --
   --  f(2n+1)=91*f(n)+179*f(n+1), n>=2
   ------------------------------------
   fD:: Integer -> Integer
   fD n | n==0   = 13
        | n==1   = 17
        | n==2   = 20
        | n==3   = 30 
        | even n = 43*fD (n `div` 2)   + 57*fD ((n `div` 2)+1) 
        | True   = 91*fD((n-1) `div` 2)+179*fD(((n-1) `div` 2)+1)
   --------------------------------------------------------------
   res:: Int -> [Integer]
   res k = take k (map (fD) [0..])
   -- ****************************
   -- Неудачные тестовые примеры:
   ------------------------------
   test = res 100
Файл с примерами можно взять здесь.

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




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