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

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

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

Возьмем, к примеру, вычисление факториала, которое использует формулу n! = 1 * 2 * … * n. То есть по сути для нахождения факториала числа мы перемножаем все числа до этого числа. Например, факториал числа 4 равен 24 = 1 * 2 * 3 * 4, а факторил числа 5 равен 120 = 1 * 2 * 3 * 4 * 5.

Определим метод для нахождения факториала:

int factorial(int n)
{
    if (n == 1)
    {
        return 1;
    }
    return n * factorial(n - 1);
}

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

На уровне языка программирования для возвращения базового варианта применяется оператор return:

if (n == 1) return 1;

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

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

return n * factorial(n - 1);

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

Используем эту функцию:

#include <stdio.h>

int factorial(int n)
{
    if (n == 1)
    {
        return 1;
    }
    return n * factorial(n - 1);
}
 
int main(void)
{
    int factorial4 = factorial(4);  // 24
    int factorial5 = factorial(5);  // 120
    int factorial6 = factorial(6);  // 720

    printf("factorial of 4: %d \n", factorial4);
    printf("factorial of 5: %d \n", factorial5);
    printf("factorial of 6: %d \n", factorial6);
     
    return 0;
}

Консольный вывод:

factorial of 4: 24
factorial of 5: 120
factorial of 6: 720

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

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

   if (n == 1) return 1;

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

   return n * factorial(n - 1);

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

   return 4 * factorial(3);

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

   factorial(3)

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

   return n * factorial(n - 1);

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

   return 3 * factorial(2);

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

   factorial(2)

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

   return n * factorial(n - 1);

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

   return 2 * factorial(1);

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

   factorial(1)

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

   if (n == 1) return 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, .... Для определения чисел этой последовательности определим следующий метод:

#include <stdio.h>

int fibonachi(int n)
{
    if (n == 0 || n == 1) return n;
    
    return fibonachi(n - 1) + fibonachi(n - 2);
}
 
int main(void)
{
    int fib4 = fibonachi(4);
    int fib5 = fibonachi(5);    
    int fib6 = fibonachi(6);

    printf("4 Fibonachi number: %d \n", fib4);
    printf("5 Fibonachi number: %d \n", fib5);
    printf("6 Fibonachi number: %d \n", fib6);
     
    return 0;
}

Здесь базовый вариант выглядит следующий образом:

if (n == 0 || n == 1) return n;

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

Рекурсии и циклы

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

int fibonachi2(int n)
{
	int result = 0;
	int b = 1;
	int tmp;

	for (int i = 0; i < n; i++)
	{
		tmp = result;
		result = b;
		b += tmp;
	}

	return result;
}

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