Рекурсивные структуры данных — это те структуры данных, которые содержат сами себя в собственных определениях. Но сегодня мы сосредоточимся на рекурсивных функциях.

Итак. Практически все функции принимают на вход некоторые данные и возвращают что-то на выходе.

функция

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

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

рекурсивная функция

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

Чтобы посчитать длину строки, функция вызывает другую функцию — strlen.

функция strlen

Данные, которые она генерирует на выходе, нужны, чтобы вывести их на экран с помощью printf.

функция printf

Особенность рекурсивной функции в том, что она вызывает сама себя. Обозначим этот процесс на картинке оранжевой стрелкой. Однако вызов самой себя предполагает ещё один рекурсивный вызов… А затем ещё один, и ещё один!

особенности рекурсивной функции

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

Рекурсия (заметки к видеолекции) - 1

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

void hi(int n)
{
	if (n <= 0)
	{
		printf("Bye!\n");
		return;
	}
	printf("Hi!\n");
	hi(n-1);		
}

Выход из рекурсии идёт первым. Если n <= 0 мы просто выводим «Bye!» и выходим из функции. Для всех других случаев функция будет выводить «Hi!» и делать рекурсивный вызов — то есть ещё один вызов функции hi с уменьшенным на единицу значением n. И так будет продолжаться до тех пор, пока n не станет равно нулю. Тогда функция напишет “Bye!” и закончит свою работу.

Рекурсия (заметки к видеолекции) - 2

Поскольку hi ничего не возвращает, мы можем не писать return явным образом.

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

Факториалом целого положительного числа n называется произведение всех целых положительных чисел, которые меньше или равны n.

Рекурсия (заметки к видеолекции) - 3

То есть

5! = 5*4*3*2*1 = 120
4! = 4*3*2*1 = 24
3! = 3*2*1 = 6 
2! = 2*1 = 2
1! = 1 

И да, по определению, 0! = 1.

Как можно написать функцию, которая рекурсивно подсчитывает факториал числа? Для начала нам нужно определить выход из рекурсии и рекурсивный вызов.

Рекурсивный вызов будет одинаков для всех случаев, кроме выхода. Это значит, нам нужно найти шаблон, который поможет нам решить задачу. На картинке выше видно, что 5! — это 4!*5, 4! — это 3!*4 и так далее, вплоть до 1!, который равен 1.

Таким образом, наш шаблон для нашего рекурсивного вызова:

n! = (n-1)! * n
Рекурсия (заметки к видеолекции) - 4

А наш выход из рекурсии или базис рекурсии будет определение факториала для единицы.

Рекурсия (заметки к видеолекции) - 5

Теперь напишем код для подсчёта факториала. Создадим функцию int factorial (int n). Для выхода из рекурсии нам нужно, чтобы выполнилось условие n == 1. В таком случае мы возвращаем 1. Потом, двигаясь по рекурсивному вызову мы будем возвращать n*factorial(n-1).

int factorial(int n)
{
    // base case
    if (n == 1)
    {
        return 1;
    }

    // recursive case
    return n * factorial(n - 1);
}

Протестируем программу. Попробуем найти 4! Для нашей функции это 4*factorial(3), а factorial(3) = factorial(2)*3, factorial(2) = factorial(1) *2. Ну а factorial(1) в свою очередь равен 1.

Мы получили эту единицу, и теперь последовательно возвращаем 2, 2*3 = 6, 6*4 = 24.

Рекурсия (заметки к видеолекции) - 6

На первых этапах знакомства с рекурсией могут быть проблемы с пониманием этого алгоритма. Важно понять, что она как бы «раскручивается» до базиса рекурсии, и затем вновь «закручивается». То есть, если нам нужно определить 5!, считайте, что 4! у нас уже есть.

Задание

Чтобы убедиться, что вы хорошо поняли рекурсию, попробуйте выполнить следующее задание:

Создать рекурсивную функцию sigma, которая считывает сумму натуральных чисел от 0 до заданного на входе числа n.

int sigma (int n);

В консоли должно отобразиться что-то в этом роде:

jharvard@run.cs50.net (~): ./a.out
Enter a positive integer: 5
15

Ну а если вы чувствуете себя совсем уверенно, попробуйте создать рекурсивную функцию бинарного поиска (помните разорванную Дэвидом книгу?).

Давайте поищем число n в заданном массиве.

bool search(int n, int array[], int lower, int upper);

Она должна возвращать true, если число n найдено, и false, если нет.

jharvard@run.cs50.net (~): ./a.out
> 4
YES