Ранее я писал обо всех возможных функциях циклов в JavaScript (https://medium.com/@rickmint/do-you-know-all-the-possible-way-to-loop-in-javascript-5ea7bdf2f74) , оставив для специальной статьи Рекурсия, которая, на мой взгляд, требует специального места. Эту фундаментальную концепцию компьютерной науки можно описать как метод решения задач, решение которого зависит от решений более мелких экземпляров той же задачи, или, проще говоря, она включает в себя функцию, вызывающую саму себя при выполнении условия и перестающую вызывать себя. когда условие не выполняется. Хотя поначалу это может показаться запутанным и довольно сложным, понимание рекурсии является ключом к написанию чистого, эффективного и масштабируемого кода, избегания повторений и написания более умного кода.

Однако я получил общее представление: что такое рекурсия?

Основная цель при использовании рекурсивной функции - решить сложную проблему, разделив ее на подзадачи, которые достаточно просты для решения и разбивки. Так называемая «разделяй и властвуй», латинская фраза, которая переводится как «разделяй и властвуй» на английском языке. С небольшими фрагментами гораздо проще обращаться, чем с большой неопределенной функцией, для переваривания которой потребуется много времени.

Рекурсивная функция обычно состоит из двух частей:

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

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

Кажется сложным. Почему я должен использовать его?

Несмотря на возможность ошибки переполнения стека, рекурсия — мощная концепция, и я могу перечислить три основные причины, по которым вы хотите их использовать:

  1. Рекурсивные функции делают код чище и легче для понимания.
  2. Рекурсия особенно полезна в задачах, которые можно естественным образом разделить на похожие подзадачи,лучше, если они связаны с деревьями, графами или алгоритмами сортировки, такими как QuickSortи MergeSort которые проще решить с помощью рекурсии.
  3. Некоторые проблемы требуют меньше памяти для рекурсивного решения, чем итеративное сокращение использования вспомогательного пространства/емкости.

Как и все в этом мире, даже рекурсия может иметь некоторые недостатки, о которых нам нужно знать, и один из них, который мы уже упоминали: риск переполнения стека. Это происходит, когда базовый случай в рекурсивной функции либо не определен, либо не достигнут, и в результате функция продолжает вызывать себя бесконечно, вызывая бесконечный цикл, который в конечном итоге приводит к сбою программы.
Также неотъемлемая сложность рекурсивной логики может создавать проблемы: рекурсивные функции трудно отслеживать и отлаживать, что делает код менее понятным по сравнению с итеративными решениями. Это особенно важно при работе в команде, где крайне важно понимать код друг друга.

Хватит болтать, давайте посмотрим на пример в действии.

Пример 1. Вычисление факториалов

Факториал числа — это произведение этого числа на факториал числа, которое меньше его на единицу.

function factorial(n) {
  if (n === 0) { // Base case
    return 1;
  } else { // Recursive case
    return n * factorial(n - 1);
  }
}
console.log(factorial(5)); // Output: 120

Пример 2: Последовательность Фибоначчи

Я знаю, это классика, но кто может устоять перед хорошей серией Фибоначчи (итальянский математик)? В этой функции каждое число в последовательности является суммой двух предыдущих.

function fibonacci(n) {
  if (n <= 1) { // Base case
    return n;
  } else { // Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}
console.log(fibonacci(6)); // Output: 8

Пример 3: вычислить степень числа

Некоторые воспоминания о старых добрых временах в начальной школе благодаря рекурсивной функции — мы можем создать метод для вычисления степени числа с использованием рекурсии.

function power(base, exponent) {
  if (exponent === 0) {
    return 1; // Base case
  } else {
    return base * power(base, exponent - 1); // Recursive case
  }
}
console.log(power(2, 3)); // Output: 8

Пример 4: Синтаксический анализ вложенного JSON

При работе с данными JSON внутри объектов могут быть вложенные объекты, и можно использовать рекурсивную функцию для извлечения определенных фрагментов данных со всех уровней вложенности, что значительно упрощает нашу жизнь!

// An example JSON object
const data = {
  name: 'John',
  details: {
    age: 30,
    interests: {
      primary: 'Coding',
      secondary: 'Hiking'
    }
  }
}

// A recursive function to get the values
function getValues(obj) {
  for (let key in obj) {
    if (typeof obj[key] === 'object') {
      getValues(obj[key]);
    } else {
      console.log(obj[key]);
    }
  }
}

getValues(data); // Output: 'John', 30, 'Coding', 'Hiking'

Я мог бы сделать это и с помощью функции reduce()!

Понимание рекурсии имеет решающее значение в разработке алгоритмов и решении проблем в компьютерном программировании — да, вы можете использовать другой способ создания функций (и я призываю вас сделать это с помощью приведенного мной примера), однако элегантность и изощренность, которых вы можете достичь с помощью рекурсии имеет небольшое количество конкурентов.
Как всегда, лучший инструмент зависит от конкретной проблемы и обстоятельств, и понимание того, когда эффективно использовать рекурсию, является важным навыком в наборе инструментов любого разработчика. Удачного кодирования! 😊🧑‍💻👩‍💻