В функциональных языках программирования для выражения повторяющегося или циклического действия часто используют рекурсию или рекурсивную функцию. Рекурсивная функция представляет такую конструкцию, при которой функция вызывает саму себя. Рекурсивные функции могут представлять неплохое решение при обходе различных древовидных представлений, к примеру, дерева каталогов и файлов.
В языке F# рекурсивная функция задается с помощью оператора rec. Например, возьмем простейшую задачу: нам надо найти сумму чисел от 0 до определенного числа. Например, если мы возьмем сумму чисео до 5, то мы получим следующую последовательность: 1 + 2 + 3 + 4 = 11. Для решения этой задачи мы можем использовать циклы, а можем использовать и рекурсию. В качестве рекурсивного решения определим следующую функцию:
let rec sum n =
if n = 1 then 1
else n + sum(n-1)
let k = 4 // находим сумму чисел до 4 включая
printfn "sum(%d) = %d" k (sum k)
Итак, оператор rec перед названием функции указывает, что функция будет ресурсивной и сможет вызывать сама себя.
При создании рекурсивной функции в ней обязательно должен быть некоторый базовый вариант, с которого начинается вычисление функции. В случае с нашей функцией это число 1, поскольку мы считаем сумму от 1 до N. Соответственно если n=1, то и результат равен 1. Возвращение базового варианта в примере выше:
if n=1 then 1
То есть, если вводимое число равно 1, то возвращается 1
Другая особенность рекурсивных функций: все рекурсивные вызовы должны обращаться к подфункциям, которые в конце концов сходятся к базовому варианту:
else n + sum(n-1)
Так, при передаче в функцию числа, которое не равно 1, при дальнейших рекурсивных вызовах подфункций в них будет передаваться каждый раз число, меньшее на единицу. И в конце концов мы дойдем до ситуации, когда число будет равно 1, и будет использован базовый вариант. Это так называемый рекурсивный спуск.
Используем эту функцию:
let rec sum n =
if n = 1 then 1
else n + sum(n-1)
let k = 4 // находим сумму чисел до 4 включая
printfn "sum(%d) = %d" k (sum k)
Рассмотрим поэтапно, что будет в случае вызова sum 4.
Сначала идет проверка, равно ли число единице:
if n=1 then 1
Но вначале n равно 4, поэтому это условие ложно, и соответственно выполняется код
else n + sum (n-1)
То есть фактически мы имеем:
else 4 + sum(3);
Далее выполняется выражение:
sum(3)
Опять же n не равно 1, поэтому выполняется код
else n + sum (n-1)
То есть фактически:
else 3 + sum(2);
Далее выполняется выражение:
sum(2)
Опять же n не равно 1, поэтому выполняется код
else n + sum (n-1)
То есть фактически:
else 2 + sum(1);
Далее выполняется выражение:
sum(1)
Теперь n равно 1, поэтому выполняется код
if n=1 then 1
И возвращается 1.
В итоге выражение
sum(4)
В реальности выливается в
4 + 3 + 2 + sum(1)
Стоит отметить, что вместо рекурсивного решения мы могли бы использовать цикл:
let sum2 n =
let mutable result = 0
for i = 1 to n do result <- (result + i)
result
let k = 5 // находим сумму чисел до 5 включая
printfn "sum(%d) = %d" k (sum2 k)
Распространенный показательный пример рекурсивных функций - вычисление факториала, которое использует формулу n! = 1 * 2 * … * n. То есть по сути для нахождения факториала
числа мы перемножаем все числа до этого числа. Например, факториал числа 4 равен 24 = 1 * 2 * 3 * 4, а факторил числа 5 равен 120 = 1 * 2 * 3 * 4 * 5.
Определим функцию для нахождения факториала:
let rec factorial n = if n=1 then 1 else n * factorial (n-1)
Здесь также базовый вариант, с которого начинается вычисление функции, - факториал числа 1 - равен 1. Факториалы всех остальных положительных чисел будет начинаться с вычисления факториала числа 1, который равен 1.
if n=1 then 1
Используем эту функцию:
let rec factorial n = if n=1 then 1 else n * factorial (n-1) printfn "Factorial of 4 = %d" (factorial 4) // Factorial of 4 = 24 printfn "Factorial of 5 = %d" (factorial 5) // Factorial of 5 = 120 printfn "Factorial of 6 = %d" (factorial 6) // Factorial of 6 = 720
Другим распространенным показательным примером рекурсивной функции служит функция, вычисляющая числа Фибоначчи. n-й член последовательности Фибоначчи определяется по формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1. То есть последовательность Фибоначчи будет выглядеть так 0 (0-й член), 1 (1-й член), 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, .... Для определения чисел этой последовательности определим следующий метод:
let rec fib n =
if n = 0 || n = 1 then n // или более кратко: if n < 2 then n
else fib(n - 1) + fib(n - 2)
printfn "4-е число Фибоначчи = %d" (fib 4) // 4-е число Фибоначчи = 3
printfn "5-е число Фибоначчи = %d" (fib 5) // 5-е число Фибоначчи = 5
printfn "6-е число Фибоначчи = %d" (fib 6) // 6-е число Фибоначчи = 8
Здесь базовый вариант выглядит следующий образом:
if n = 0 || n = 1 then n
Либо можно объединить оба варианта:
if n < 2 then n
То есть, если мы ищем нулевой или первый элемент последовательности, то возвращается это же число - 0 или 1. Иначе возвращается
результат выражения fib(n - 1) + fib(n - 2)
Рекурсия позволяет элегантным образом решить множество задач. Тем не менее в стандартном виде, в каком было продемострировано выше, она имеет недостаток - каждый новый вызов функции приводит к тому, что для этой функции (параметров, переменных) выделяется место в стеке. Поскольку при рекурсии функция вызывает саму себя, то очень глубокой вложенности вызовов функций мы можем быстро прийти к исчерпанию места в стеке, и соответственно программа завершится с ошибкой. Чтобы этого не произошло, F# предоставляет возможность использовать хвостовую ресурсию (tail recursion), при которой рекурсивный вызов является последним выражением в функции. В этом случае рекурсия обычно компилируется в цикл наподобие while, и соответственно проблемы со стеком не произойдет. Например, оптимизируем рекурсивную функцию sum из начала статьи:
let sum2 num =
let rec tailSum n acc =
if n = 0 then acc
else tailSum (n-1) (acc + n)
tailSum num 0
printfn "sum2(4) = %d" (sum2 4)
printfn "sum2(5) = %d" (sum2 5)
printfn "sum2(6) = %d" (sum2 6)
Для использования хвостовой ресурсии в функции sum2 определена вложенная функция tailSum. Она принимает два параметра - промежуточное число, для которого надо подсчитать результат, и параметр acc - накопленная сумма.
Если переданное число равно 0, то соответственно нам нет смысла дольше считать (так как расчет идет начиная с 0), поэтому возвращаем накопленную сумму:
if n = 0 then acc
При любом другом значении n к ранее накопленной сумме прибавляем n и передаем результат второму параметру. А от числа n вычитаем 1
else tailSum (n-1) (acc + n)
В конце запускаем рекурсивную функцию tailSum:
tailSum num 0
Параметр num берется из внешней функции sum2, а накопленная сумма по умолчанию равна 0.
Аналогично можно оптимизировать и другие функции. Например, функция факториала:
let factorial x =
let rec tailFactorial x acc =
if x <= 1 then acc
else
tailFactorial (x - 1) (acc * x)
tailFactorial x 1
Функция фибоначчи
let fib n =
let rec tailFib x acc y =
if y =0 then acc
else tailFib acc (acc+x) (y-1)
tailFib 1 0 n
