Рекурсия

Рекурсия - математический механизм, в котором для решения задачи из функции вызывается та же самая функция

Рекурсивная функция - вызов функции из нее же самой.

Рекурсивная функция всегда должна состоять из:

1. Условие остановки
2. Шаг рекурсии

Пример реализации рекурсии:

#include <stdio.h>
void rec(int n)
{
   if(n>0) rec(n-1);
   printf("%5d",n);
}
int main(void)
{
    rec(3);
    return 0;


}

Вычисление факториала

Классическим примером использования рекурсии является вычисление факториала. Код итерационного варианта может быть таким:

unsigned int factorial(unsigned int n)
{
    unsigned int i, fact=1;
    for(i=2;i<=n;i++)
        fact*=i;
    return fact;
}

Функция для рекурсивного вычисления факториала:

unsigned int factorial(unsigned int n)
{
    printf("%d\n",n);
    if(n<=1) // Условие остановки
        return 1;
    int _f = n * factorial(n-1);
    printf("%d*factorial(%d)=%d\n",n,n-1,_f);
    return _f; // Шаг
}

Разбирая данную фукцию по шагам получается следующая картина:

А в стеке памяти в определенный момент времени храниться одновременно 3 экземпляра функции:

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