Рекурсивные функции

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

В языке F# рекурсивная функция задается с помощью оператора rec. Рассмотрим ряд примеров.

Рекурсивная функция факториала

Возьмем вычисление факториала, которое использует формулу 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)

Итак, оператор rec перед названием функции указывает, что функция будет ресурсивной и сможет вызывать сама себя.

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

if n=1 then 1

То есть, если вводимое число равно 1, то возвращается 1

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

else n * factorial (n-1)

Так, при передаче в функцию числа, которое не равно 1, при дальнейших рекурсивных вызовах подфункций в них будет передаваться каждый раз число, меньшее на единицу. И в конце концов мы дойдем до ситуации, когда число будет равно 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

Рассмотрим поэтапно, что будет в случае вызова factorial 4.

1. Сначала идет проверка, равно ли число единице:

   if n=1 then 1

   Но вначале n равно 4, поэтому это условие ложно, и соответственно выполняется код

   else n * factorial (n-1)

   То есть фактически мы имеем:

   else 4 * factorial(3);

2. Далее выполняется выражение:

   factorial(3)

   Опять же n не равно 1, поэтому выполняется код

   else n * factorial (n-1)

   То есть фактически:

   else 3 * factorial(2);

3. Далее выполняется выражение:

   factorial(2)

   Опять же n не равно 1, поэтому выполняется код

   else n * factorial (n-1)

   То есть фактически:

   else 2 * factorial(1);

4. Далее выполняется выражение:

   factorial(1)

   Теперь n равно 1, поэтому выполняется код

   if n=1 then 1

   И возвращается 1.

В итоге выражение

factorial(4)

В реальности выливается в

4 * 3 * 2 * factorial(1)

Рекурсивная функция Фибоначчи

Другим распространенным показательным примером рекурсивной функции служит функция, вычисляющая числа Фибоначчи. 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
    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

То есть, если мы ищем нулевой или первый элемент последовательности, то возвращается это же число - 0 или 1. Иначе возвращается результат выражения fib(n - 1) + fib(n - 2)