Рекурсия

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

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

 
  factorial :: Integer -> Integer
  factorial n = if n == 0 then 1 else n * factorial (n - 1)
 
(Заметьте, что мы пишем factorial (n - 1), а не factorial n - 1 — вспомните о приоритетах операций.) Использование рекурсии может вызвать трудности. Концепция рекур-
сии напоминает о применяющемся в математике приеме доказательства по индукции. В нашем определении факториала мы выделяем «базу индукции» (случай n == 0) и «шаг индукции» (переход от factorial n к factorial (n - 1). Выделение таких компонент — важный шаг в определении рекурсивной функции.