На этом шаге мы рассмотрим пример такой трансформации.
Существуют редкие случаи, когда с помощью трансформации программ рекурсия высших порядков может быть приведена к простой рекурсии.
Пример 1 (Э.Дейкстра).
Рассмотрим следующие рекуррентные соотношения:
f(0)=0, f(1)=1, f(2n)=f(n), f(2n+1)=f(n)+f(n+1).
Преобразуем эту рекурсию высшего порядка в простую рекурсию.
Рассмотрим новую функцию
g(n,i,j)=i * f(n)+j * f(n+1),
f(n)=g(n,1,0).
Определим рекуррентные соотношения для функции g():
(1) g(2n,i,j)=i * f(2n)+j * f(2n+1)=i * f(n)+j * f(n)+j * f(n+1)=
=(i+j)f(n)+j 77 0f(n+1)=g(n,i+j,j);
(2) g(2n+1,i,j)=i * f(2n+1)+j * f(2n+2)=i * f(n)+i * f(n+1)+j * f(n+1)=
=i * f(n)+(i+j) * f(n+1)=g(n,i,i+j).
Итак, получена простая рекурсия
g(0,i,j)=j, g(2n,i,j)=g(n,i+j,j), g(2n+1,i,j)=g(n,i,i+j),
Приведем демонстрационный пример.
-- Демонстрация трансформации рекурсии высшего порядка -- в простую рекурсию на примере задачи вычисления -- значения функции Дейкстры -- -- f(0)=0, f(1)=1, -- -- f(2n)=f(n), -- -- f(2n+1)=f(n)+f(n+1), -- -- которая преобразуется в задачу вычисления значения -- функции -- -- g(0,i,j)=j, -- g(2n) =g(n,i+j,j), -- g(2n+1) =g(n,i,i+j). -- -- Теперь значение функции f() находится так: -- -- f(n)=g(n,1,0) -- ************************** fDejikst:: Integer -> Integer fDejikst n | n==0 = 0 | n==1 = 1 | even n = fDejikst (n `div` 2) | True = fDejikst ((n-1) `div` 2)+ fDejikst (((n-1) `div` 2)+1) --------------------------------------------------- gDejikst:: Integer -> Integer -> Integer -> Integer gDejikst n i j | n==0 = j | even n = gDejikst (n `div` 2) (i+j) j | True = gDejikst ((n-1) `div` 2) i (i+j) -- ******************************************************* -- Неудачные тестовые примеры: ----------------------------------------------------- test = fDejikst 12 == gDejikst 12 1 0 && fDejikst 234 == gDejikst 234 1 0 && fDejikst 1234 == gDejikst 1234 1 0 && fDejikst 12345 == gDejikst 12345 1 0 && fDejikst 123456 == gDejikst 123456 1 0 && fDejikst 123456789 == gDejikst 123456789 1 0
На следующем шаге мы закончим изучение этого вопроса.
