Тема 6. Рекурсивные программы. Методы доказательства их правильности

Понятие рекурсивных программ. Способы их описания

Язык описания рекурсивных программ

Введем упрощенный язык программирования для иллюстрации работы рекурсивных программ. Программа на этом языке состоит из определения функции следующего вида:

F ( x₁, x₂, … x_n) = if <условие1> then <выражение1>

else if <условие2> then <выражение2>

. . . .

                              if <условие N> then <выражениеN>

else <выражение N+1>

В данном выражении последовательно проверяются условия. Если i-ое условие выдает истину, то функция F выдает значение выражения i. Если ни одно из условий не выдает истину, то функция выдает значение выражения N+1. Рекурсия вводится в этот язык следующим образом: функция F может входить как часть в любом из выражений или условий в программе. Такое появление F называется рекурсивным обращением к этой функции. Дополнительно для каждой такой рекурсивной программы необходимо указать область определения, т.е. указать для каких аргументов х₁,…х_n применима программа.

Примеры рекурсивных программ

1. Рассмотрим программу, применимую  целого:

F ( x) = if х=0 then 1

else х·F(х-1)

Для иллюстрации работы данной программы выполним ее, например, для х=4:

2. Функция Аккермана. Эта функция применима  целых.

А(х,у) = if х=0 then у+1

else if y=0 then A(x-1,1)

else A(х -1, A(x, y-1))

Проследим, каким образом выполняется эта программа для х=1, у=2.

А(1,2)=А(0, А(1,1))=А(0, А(0, А(1,0)))=

=А(0, А(0, А(0,1)))=А(0, А(0,2))= А(0,3) =4

Из этого примера видно, что при вычислении рекурсивных функций могут возникать неоднозначности, связанные с последовательностью вычисления аргументов. Например, при обращении А(0, А(1,1)) мы предполагали, что А(1,1) должна быть вычислена прежде, чем будут продолжены вычисления, относящиеся к внешнему обращению к функции А. Если отдать предпочтение вычислениям, связанным с внешним обращением, то вычисления будут производиться в следующем порядке:

А(1, 2) = А(0, А(1,1)) = А(1,1) + 1 =

= А(0, А(1,0)) + 1= (А(1,0) +1) + 1 =

= А(0,1) + 2 = 2 + 2 = 4

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

Рассмотрим следующую функцию, применимую  целых:

F ( x,у) = if х=0 then 0

else F(0, F(х,у))

Проследим за вычислением F, используя два различных правила вычисления:

1) при предпочтении внешнему обращению

F (1,1) = F(0, F(1,1))=0;

2) при предпочтении внутреннему обращению.

F (1,1) = F(0, F(1,1))= F(0, F(0,F(1,1)))=…

Таким образом, в первом случае последовательность конечна и функция А=0, во втором случае вычисления не заканчиваются.

Для того чтобы устранить неопределенность, необходимо задать правила вычисления. Большинство языков программирования при обращении к функции (процедуре) предварительно вычисляют аргументы, отдавая тем самым предпочтение внутреннему вызову.

⇐ Предыдущая45678910111213Следующая ⇒

Поделиться: