Современные информационные технологии/ 2. Вычислительная техника и программирование

 

Бурлибаева Ш.М., Каргабаева Д.Т.

 

Рекурсия в функциональном языке Haskell

 

Существует два основных вида языков программирования: императивные и декларативные.

Императивные языки - это языки, в которых  программистом задается пошаговый алгоритм решения задачи ("как" решить задачу), это языки программирования, вроде C, C++, C#, Pascal, Basic и множество других. Главным отличием императивных языков программирования является то, что на них мы говорим, что нужно сделать, но не указываем, что же должно получиться в результате.

А декларативные языки программирования наоборот, дают возможность нам описать состояния, которое мы хотим получиться, но не требуют от нас указывать, как к нему прийти. Примеры таких языков: функциональные(F#, LISP / Scheme, ML и друзья, Haskell) и логические (Пролог)

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

Рекурсия является простой, если вызов функции встречается в некоторой ветви лишь один раз. Простой рекурсии в процедурном программировании соответствует обыкновенный цикл. Например, задача нахождения значения факториала n! сводится к нахождению значения факториала (n-1)! и умножения найденного значения на n.

Рассмотрим простейший пример – задачу вычисления факториала. Приведем два типичных варианта ее решения: на С и на Haskell'e.

int fact (int n) {

  int i, mult = 1;

  for(i=l; i<=n; i++)

     mult = i * mult;

  return mult;

}

 

программа на С

fact :: Int -> Int

fact 1 = 1

fact n = n * fact (n-l)

 

 

 

 

программа на Haskell'e

Программа на Haskell'e несколько короче, но значительно важнее то, что она имеет несравненно более ясный смысл. Фактически, это просто определение или спецификация того, что такое факториал. В этом определении не содержится никаких элементов, выходящих за рамки самой задачи. Напротив, в программе на С конструкция цикла и меняющаяся переменная цикла не связаны непосредственно с логикой задачи. Если необходимо доказать корректность программы, доказать, что она вычисляет именно факториал, то для варианта, написанного на С, сделать это на порядок сложнее. Вариант же на Haskell'e практически не требует доказательства.

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

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

Вот несколько примеров простой рекурсии.

1.   Возведение числа x в степень n с помощью умножения (рекурсия по аргументу):

step  ::  Double -> Integer -> Double

step x 0 = 1

step x n = step x (n-1) * x

Результат :

Строчка  step x 0 = 1 обозначает, что x0=1 (любое число в нулевой степени равно 1). А строчка  step x n = step x (n-1) * x обозначает, что xn=x(n-1)*х (значение x в степени n вычисляется возведением x в степень n-1 и умножением результата на х).

2.   Замена в строке указанного символа на заданный (рекурсия по значению):

samenaSim :: Char -> Char -> String -> String

samenaSim a b [] = []
samenaSim a b (h:t) = if h == a then b : samenaSim a b t else h :  samenaSim a b t

Результат :

Здесь а- заменяемый символ, b- символ, на который надо заменить, h- любой символ строки

3.   Определить список треугольных чисел  (n-ое   треугольное   число  tn  равно   количеству   одинаковых   монет,   из   которых   можно   построить равносторонний  треугольник, на  каждой  стороне  которого укладывается  n  монет. Нетрудно  убедиться, что t1 = 1 и tn = n + tn−1).

treugShis :: Integer -> [Integer]

t 1 = 1

t n = n + t (n-1)

treugShis 0 = []

treugShis n = treugShis (n-1) ++ [t n]

Результат :

Литература

1.    С.В. Зыков.  Введение в теорию программирования. Функциональный подход

2.    Л.В. Городняя. Основы функционального программирования

3.    С. Сильван. Сильные стороны языка Haskell