Эта статья предназначена для того, чтобы помочь понять рекурсию и ее особенности, которые делают ее полезным (хотя иногда и немного сложным) инструментом в программировании.

Во-первых, что такое рекурсия?

Существуют разные типы рекурсии, но основной принцип заключается в том, что рекурсивная функция — это функция, которая вызывает сама себя либо непосредственно в той же функции (прямая рекурсия), либо косвенная рекурсия (функция 1 вызывает функцию 2, которая вызывает функцию 1 и т. д.).

пример:

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

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

Стек, что это такое?

Проще говоря, стек — это структура данных в соответствии с принципом LIFO (последним пришел — первым вышел). Как и на этом изображении, первое, что мы вталкиваем в стек, не может вытолкнуть, если за ним что-то вставлено. В порядке этого изображения мы сначала нажали Main, затем Call 1, Call 2, Call 3, Call 4, поэтому мы должны сначала вывести Call 4, затем Call 3, Call 2, Call 1 и, наконец, Main.

Все еще немного запутался? Как насчет примера?

Выполнение функции

Возьмем _pow_recursion(3, 3), мы поместим его возвращаемое значение в стек, но нам нужно знать возвращаемое значение _pow_recursion(3, 2), чтобы вычислить его.

Мы берем _pow_recursion(3, 2), помещаем возвращаемое значение в стек, но нам нужно знать возвращаемое значение _pow_recursion(3, 1), чтобы вычислить его.

Мы берем _pow_recursion(3, 1), помещаем возвращаемое значение в стек, но нам нужно знать возвращаемое значение _pow_recursion(3, 0), чтобы вычислить его.

А потом :

Однако с _pow_recursion(3, 0) мы видим, что y = 0, что является условием остановки… поэтому мы возвращаем 1.

Заключение

Рекурсивная функция — это полезный способ уменьшить временную сложность (Big O) функции, поскольку она имеет временную сложность O (n). Он часто используется для функции сортировки.

Основным недостатком рекурсивной функции является используемая память, поскольку она должна поддерживать стек.

Я надеюсь, что эта статья была полезна для вас.