Давайте посмотрим, что такое функции 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 слов для каждого слабого места, связанного с разными темами (в основном с технологиями и финансами).