Давайте посмотрим, что такое функции Recursion и Recursive!
Что такое рекурсия?
Когда функция прямо или косвенно вызывает сама себя, это называется рекурсией, а сама функция называется рекурсивной функцией.
Структура рекурсивной функции
Есть три основных компонента рекурсивной функции:
- Вызов функции внутри функции (функция должна вызывать сама себя).
- Базовое состояние
- Тип возврата функции
Type function_name(params){ if (<base_condition>){ -------- -------- function_name(params') -------- -------- } }
Базовое условие — важная часть рекурсивной функции, которая помогает завершить функцию в какой-то момент. Если базовое условие неверно, оно (то есть не завершающееся) может привести к созданию бесконечного цикла.
Разница между итеративной функцией и рекурсивной функцией
Рекурсивная функция имеет два сегмента кода, восходящий и нисходящий, тогда как итеративная функция имеет только восходящий сегмент кода.
Типы рекурсии
- Хвостовая рекурсия. Когда рекурсивный вызов является последним оператором рекурсивной функции, он называется хвостовой рекурсией.
function_name(params) { if (<base_condition>) { ----- ----- ----- function_name(params); } }
Все операции в хвостовой рекурсии выполняются во время вызова времени, и никакие операции не выполняются во время возврата.
- Головная рекурсия. Когда рекурсивный вызов является первым оператором рекурсивной функции, он называется головной рекурсией.
function_name(params) { if (<base_condition>) { function_name(params); ----- ----- ----- } }
Все операции в Head Recursion выполняются при возврате. Во время вызова операции с кодом не выполняются.
- Рекурсия по дереву. Когда рекурсивная функция вызывает себя более одного раза в функции, это называется рекурсией по дереву.
function_name(params) { if (<base_condition>) { function_name(params); ----- ----- function_name(params); ----- ----- } }
- Косвенная рекурсия — когда одна функция вызывает другую функцию, а другая вызывает обратно, первый формирующий цикл называется косвенной рекурсией. Могут быть задействованы более 2 функций.
function_name1(params) { if ( <base_condition>) { ---- ---- function_name2(params); ---- } } function_name2(params) { if ( <base_condition>) { ---- ---- function_name1(params); ---- } }
- Вложенная рекурсия. Когда рекурсивный вызов передается в качестве параметра рекурсивной функции, он называется вложенной рекурсией.
function_name(params) { if (<base_condition>){ ---- ---- function_name(function_name(params)); ---- } }
Факты о рекурсии
- Некоторые компиляторы пытаются преобразовать вашу хвостовую рекурсию в объектный код и, в конечном итоге, в циклы, уменьшая временную сложность программ.
- Рекурсия использует стек для своего функционирования
- Древовидная структура данных в основном используется с рекурсией для всех операций.
Я буду рад услышать отзывы на @HimanshuKhaita4 по вышеприведенному контенту. Кроме того, я буду публиковать по 5 слов для каждого слабого места, связанного с разными темами (в основном с технологиями и финансами).