С - Рекурсия

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

void recursion() {
   recursion(); /* function calls itself */
}

int main() {
   recursion();
}

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

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

Числовой факториал

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

Живая демонстрация

#include <stdio.h>

unsigned long long int factorial(unsigned int i) {

   if(i <= 1) {
      return 1;
   }
   return i * factorial(i - 1);
}

int  main() {
   int i = 12;
   printf("Factorial of %d is %d\n", i, factorial(i));
   return 0;
}

Когда приведенный выше код скомпилирован и выполнен, он дает следующий результат —

Factorial of 12 is 479001600

Ряд Фибоначчи

В следующем примере создается ряд Фибоначчи для заданного числа с использованием рекурсивной функции —

Живая демонстрация

#include <stdio.h>

int fibonacci(int i) {

   if(i == 0) {
      return 0;
   }
	
   if(i == 1) {
      return 1;
   }
   return fibonacci(i-1) + fibonacci(i-2);
}

int  main() {

   int i;
	
   for (i = 0; i < 10; i++) {
      printf("%d\t\n", fibonacci(i));
   }
	
   return 0;
}

Когда приведенный выше код скомпилирован и выполнен, он дает следующий результат —

0	
1	
1	
2	
3	
5	
8	
13	
21	
34