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

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

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

Следующий пример демонстрирует прямую рекурсию:

int func (int a)  
{  
    //операторы  
  
    func(a-1);  
  
    // операторы  
  
    return 0;  
}

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

int func (int a)  
{  
    //операторы  
  
    func_new(a);  
  
    // операторы  
  
    return 0;  
}  
  
int func_new(int b)  
{  
    //операторы  
  
    func(b-1);  
  
    //операторы  
  
    return 0;  
}

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

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

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

#include   
  
int main()  
{  
 int a = 0, i = 0, fact = 1;  
 printf("Введите число: ");  
  
 scanf("%d", &a);  
   
 for(i=1; i<=a; i++)  
 {  
 fact = fact * i;  
   
 }  
 printf("Факториал числа равен: %d ", fact);  
 return 0;  
}

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

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

#include   
  
int factorial (int b)  
{  
 if(!b)  
 return 1;  
   
 return (b * factorial(b-1));  
}  
  
int main()  
{  
 int a = 0, fact = 1;  
 printf("Введите число: ");  
  
 scanf("%d", &a);  
   
 fact = factorial(a);  
   
 printf("Факториал числа равен: %d ", fact);  
 return 0;  
}

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

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

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

Таким образом, если посмотреть в общем, вот как эти вызовы функций накапливаются:

• 5 * factorial(4)
• 4 * factorial(3)
• 3 * factorial(2)
• 2 * factorial (1)
• 1 * factorial (0)

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

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

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

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

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

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

Заключение

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