Рекурсия


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

Типичные примеры использования рекурсии:

  • Прохождение рекурсивных структур данных, таких как связанные списки, двоичные деревья и т. Д.
  • Изучение возможных сценариев в таких играх, как шахматы

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

Например, эта функция будет выполнять умножение путем рекурсивного добавления:

#include <stdio.h>

unsigned int multiply(unsigned int x, unsigned int y)
{
    if (x == 1)
    {
        /* Terminating case */
        return y;
    }
    else if (x > 1)
    {
        /* Recursive step */
        return y + multiply(x-1, y);
    }

    /* Catch scenario when x is zero */
    return 0;
}

int main() {
    printf("3 times 5 is %d", multiply(3, 5));
    return 0;
}

Упражнение

Определите новую функцию, которая будет вычислять факториал рекурсивным умножением (5! = 5 x 4 x 3 x 2 x 1). Обратите внимание, что по соглашению факториал 0 равен 1 (0! = 1).factorial()