Учебник по программированию на C для Linux. Часть 18. Рекурсивные функции

На этой странице

Заключение

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

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

Ниже приведен пример прямой рекурсии:

int func (int a)
{
    //statements

    func(a-1);

    // statements

    return 0;
}

И вот пример косвенной рекурсии:

int func (int a)
{
    //statements

    func_new(a);

    // statements

    return 0;
}

int func_new(int b)
{
    //statements

    func(b-1);

    //statementsur

    return 0;
}

Как уже упоминалось в начале, рекурсия помогает вам создавать компактный код, который не только легко написать, но и легко понять и просмотреть. Давайте возьмем пример, чтобы сделать это преимущество более очевидным.

Я уверен, что вы все наверняка слышали о концепции факториала. Для тех, кто не знает, факториал — это результат, который вы получаете, когда умножаете целое число на все положительные целые числа, меньшие его. Например, факториал числа 5 равен 5x4x3x2x1, что равно 120.

Вот простой код для нахождения факториала числа:

#include <stdio.h>

int main()
{
 int a = 0, i = 0, fact = 1;
 printf("Enter a number: ");

 scanf("%d", &a);
 
 for(i=1; i<=a; i++)
 {
 fact = fact * i;
 
 }
 printf("Factorial of the number is: %d ", fact);
 return 0;
}

Обратите внимание, что этот код предназначен только для того, чтобы вы знали, как можно вычислить факториал числа с помощью программы на языке C. Программа не заботится о крайних случаях, которые могут повлиять на точность получаемого результата.

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

#include <stdio.h>

int factorial (int b)
{
 if(!b)
 return 1;
 
 return (b * factorial(b-1));
}

int main()
{
 int a = 0, fact = 1;
 printf("Enter a number: ");

 scanf("%d", &a);
 
 fact = factorial(a);
 
 printf("Factorial of the number is: %d ", fact);
 return 0;
}

Как видите, функция factorial, которая фактически вычисляет факториал, очень компактна. И если внимательно присмотреться, то это тоже очень легко понять.

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

Затем оператор return содержит выражение, умножающее 5 на возвращаемое значение factorial(4). Итак, теперь функция factorial выполняется еще раз, и мы получаем следующее выражение: return (4 * factorial(3)). А потом снова эти действия повторяются.

Итак, если вы посмотрите широко, вот как эти вызовы функций складываются:

5 * факториал(4)
4 * факториал(3)
3 * факториал(2)
2 * факториал (1)
1 * факториал (0)

Теперь, когда factorial(0) выполняется, условие if в функции factorial становится истинным, и возвращается значение 1. Итак, вот как завершаются перечисленные выше вызовы (сравните последнюю запись в предыдущем списке с первой записью в этом списке и т. д.):

1 * 1
2 * (1*1)
3 * (2*(1*1))
4 * (3*(2*(1*1)))
5 * (4 * (3*(2*(1*1))))

Фактически это 5 * 4 * 3 * 2 * 1, что, в свою очередь, равно 120, факториалу 5.

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

Например, в приведенном выше примере до завершения вызова factorial(0) все предыдущие вызовы factorial ожидали завершения обработки функции. Не говоря уже о том, что автоматические или локальные переменные занимают память при каждом сделанном рекурсивном вызове.

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

Заключение

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