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

Определение.

(1) Рекурсией высших порядков называется такая форма рекурсии, при которой рекурсивный вызов функции является аргументом вызова этой же самой функции на определённом уровне рекурсии.
(2) Функции, не обладающие рекурсией высших порядков, называются функциями с рекурсией нулевого порядка.

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

   -- Демонстрация сложной рекурсии на числовых структурах
   -- на примере вычисления значения функции "91-МакКарти" 
   -- 
   --   F(n)=If n>100
   --          then n-10
   --          else F(F(F(n+21)))
   -- ***************************
   f91:: Integer -> Integer 
   f91 n | n>100 = n-10
         | True  = f91 (f91 (f91 (n+21)))
   -- ***********************************
   -- Неудачные тестовые примеры:
   ------------------------------
   test =   f91  11==91 
         && f91  22==91 
         && f91  96==91 
         && f91  99==91
         && f91 101==91 
         && f91 102==92

Файл с примерами можно взять здесь.

Продемонстрируем с помощью рекурсии высших порядков тот факт, что интерпретатор языка Haskell использует нормальный порядок β-редукции при вычислениях.

   -- Демонстрация принятой в языке Haskell семантики вы-
   -- числений, заключающейся в выборе для вычислений при
   -- рекурсивном вызове самой внешней функции (так назы-
   -- ваемая нормальная форма бета-редукции).
   --   Поясним сказанное с помощью следующей функции:
   --                                  
   --          ¦1, если x=0;
   --   f(x,y)=¦
   --          ¦f(x-1,f(x,y)), если x>0.
   --
   --   Значение f(1,0) можно вычислить двумя способами:
   --   (1) с помощью нормальной формы бета-редукции:
   --
   --       f(1,0)=f(0,f(1,0))=1;
   --
   --   (2) с помощью аппликативного порядка редукции:
   --
   --       f(1,0)=f(0,f(1,0))=f(0,f(0,f(1,0)))=
   --             =f(0,f(0,f(0,f(1,0))))=...
   --
   -- Возникает неоднозначность процесса вычисления...
   -- ************************************************
   func1:: Integer -> Integer -> Integer
   func1 x y | x==0 = 1
             | True = func1 (x-1) (func1 x y)
   ------------------------------------------
   func2:: Integer -> Integer -> Integer
   func2 x y | y==0 = 1
             | True = func2 (func2 x y) (y-1) 
   ------------------------------------------
   -- Неудачные тестовые примеры:
   ------------------------------
   test1 =   func1   1  0 == 1
          && func1   1  1 == 1
          && func1   2  0 == 1
          && func1 123 34 == 1
   ---------------------------
   test2 =   func2  1   0 == 1
          && func2  1   1 == 1
          && func2  0   2 == 1
          && func2 34 123 == 1

Файл с примерами можно взять здесь.

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

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