Привет, рекурсия!

В предыдущей главе мы кратко затронули рекурсию. Теперь мы изучим её более подробно, узнаем, почему она так важна для языка Haskell и как мы можем создавать лаконичные и элегантные решения, думая рекурсивно.

Если вы всё ещё не знаете, что такое рекурсия, прочтите это предложение ещё раз. Шучу!.. На самом деле рекурсия – это способ определять функции таким образом, что функция применяется в собственном определении. Стратегия решения при написании рекурсивно определяемых функций заключается в разбиении задачи на более мелкие подзадачи того же вида и в попытке их решения путём разбиения при необходимости на ещё более мелкие. Рано или поздно мы достигаем базовый случай (или базовые случаи) задачи, разбить который на подзадачи не удаётся и который требует написания явного (нерекурсивного) решения.

Многие понятия в математике даются рекурсивно. Например, последовательность чисел Фибоначчи. Мы определяем первые два числа Фибоначчи не рекурсивно. Допустим, F(0) = 0 и F(1) = 1; это означает, что нулевое и первое число из ряда Фибоначчи – это ноль и единица. Затем мы определим, что для любого натурального числа число Фибоначчи представляет собой сумму двух предыдущих чисел Фибоначчи. Таким образом, F(n) = F(n – 1) + F(n – 2). Получается, что F(3) – это F(2) + F(1), что в свою очередь даёт (F(1) + F(0)) + F(1). Так как мы достигли чисел Фибоначчи, заданных не рекурсивно, то можем точно сказать, что F(3) равно двум.

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