На приведенном выше рисунке показано, как работает рекурсия. Будь осторожен! Рекурсия — это не повторение, рекурсия — это искусство вызова самого себя, но в пути есть закономерность.

Рекурсия — это процесс определения чего-либо в терминах самого себя. Он неоднократно вызывает механизм и, следовательно, увеличивает накладные расходы на вызовы функций. Другое определение может быть таким: «Метод, при котором решение проблемы зависит от решений более мелких экземпляров той же проблемы».

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

Как сделать рекурсию?

Нам нужно рассмотреть два шага:
1. Поиск базового случая.
2. Поиск рекурсивного шага.

Хорошо, посмотрим, как рекурсивная функция будет выглядеть в стеке. Мы сосредоточимся на функции _pow_recursion, которая возвращает результат основания в степени (показатель степени).

Как вы видели в приведенной выше функции, основание представлено «x», а показатель степени представлен «y».

Теперь мы возьмем пример. Как насчет небольшой операции? 3 в 4 степени.

Итак, мы упорядочиваем процесс операции в стеке, как показано на рисунке ниже:

Рекурсия останавливает свои шаги, потому что (y == 0) и возвращает 1 на своем последнем шаге. Теперь настало время внимательно изучить возврат каждого шага или входа в стек.

_pow_recursion(3, 4) -> return(_pow_recursion(3, 3) * 3)
_pow_recursion(3, 3) -> return(_pow_recursion(3, 2) * 3)
_pow_recursion(3, 2) -> return(_pow_recursion(3, 1) * 3)
_pow_recursion(3, 1) -> return(_pow_recursion(3, 0) * 3)
_pow_recursion(3, 0) -> возврат(1)

Наконец, основная функция, которая вызывает функции _pow_recursion, получает следующий результат:

return (27 * 3)

Таким образом, мы получаем результат нашей операции: 27 * 3 = 81.
И, очевидно, 3 в 4-й степени равно 81. Отличная работа!

Эй... Подожди! Почему 81.000000?

Ну не забудь! Функция _pow_recursion:

float _pow_recursion(float x, float y);

Итак, функция возвращает число с плавающей запятой, и по умолчанию число с плавающей запятой имеет 6 знаков после запятой.

Преимущества рекурсии

  1. Рекурсивные функции делают код чистым и элегантным.
  2. Сложная задача может быть разбита на более простые подзадачи с помощью рекурсии.
  3. Генерация последовательности проще с рекурсией, чем с использованием какой-либо вложенной итерации.

Недостатки рекурсии

  1. Иногда логику рекурсии трудно понять.
  2. Рекурсивные вызовы дороги (неэффективны), так как занимают много памяти и времени.
  3. Рекурсивные функции трудно отлаживать.

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

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

Спасибо за прочтение!