На приведенном выше рисунке показано, как работает рекурсия. Будь осторожен! Рекурсия — это не повторение, рекурсия — это искусство вызова самого себя, но в пути есть закономерность.
Рекурсия — это процесс определения чего-либо в терминах самого себя. Он неоднократно вызывает механизм и, следовательно, увеличивает накладные расходы на вызовы функций. Другое определение может быть таким: «Метод, при котором решение проблемы зависит от решений более мелких экземпляров той же проблемы».
Это повторение может быть дорогостоящим как с точки зрения процессорного времени, так и с точки зрения объема памяти.
Как сделать рекурсию?
Нам нужно рассмотреть два шага:
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 знаков после запятой.
Преимущества рекурсии
- Рекурсивные функции делают код чистым и элегантным.
- Сложная задача может быть разбита на более простые подзадачи с помощью рекурсии.
- Генерация последовательности проще с рекурсией, чем с использованием какой-либо вложенной итерации.
Недостатки рекурсии
- Иногда логику рекурсии трудно понять.
- Рекурсивные вызовы дороги (неэффективны), так как занимают много памяти и времени.
- Рекурсивные функции трудно отлаживать.
Это краткая статья о том, как работает рекурсия в памяти компьютера. Рекурсия — это ворота для других сложных операций, таких как бинарные деревья.
Как видите, функция binary_tree_delete вызывает себя до тех пор, пока существует левая часть дерева, а затем те же функции вызывают себя, пока существует правая часть дерева. Если последнее обозначение не существует, то возвращается освобождение узлов.
Спасибо за прочтение!