Вы знаете, что Javascript изначально не поддерживает рекурсию.

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

В этом сообщении блога мы обсудим рекурсию, как она работает и как ее можно реализовать в JavaScript. Мы также рассмотрим некоторые распространенные примеры рекурсивных функций и их приложений.

Что такое рекурсия?

Рекурсия — это метод программирования, при котором функция вызывает себя для решения проблемы. Функция, которая иногда вызывает себя даже более одного раза, называется recursive..

Чтобы понять рекурсию, вам нужно понять две концепции. base case и recursive case. Базовый случай — это точка, в которой рекурсия останавливается. Рекурсивный случай — это когда функция должна будет вспомнить себя.

Как работает рекурсия

Процесс разбиения проблемы на более мелкие подзадачи называется деревом рекурсии.

Дерево рекурсии — это древовидная структура, представляющая рекурсивные вызовы, сделанные функцией. Каждый узел представляет собой вызов функции. Корневой узел представляет начальный вызов функции, а конечные узлы представляют базовые случаи.

Реализация рекурсии в JavaScript

Чтобы реализовать рекурсию в js, нам нужно определить функцию, которая вызывает себя. Функция должна включать базовый случай, который остановит рекурсию. Вот пример рекурсивной функции, вычисляющей факториал числа:

function factorial(n) {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

В приведенной выше функции базовый случай — это когда n === 0 функция возвращает 1, что является факториалом 0. Рекурсивный случай — это когда n больше 0. Это означает, что функция будет вызываться до тех пор, пока n === 0. Функция возвращает значение результат вызова функции с текущим значением n.

Вот пример вызова функции factorial:

console.log(factorial(5)); // Output: 120

Этот код выведет 120, что является факториалом 5.

Еще несколько примеров.

1. Последовательность Фибоначчи

Ряд Фибоначчи — это последовательность чисел, в которой каждое число является суммой двух предыдущих чисел. Первые два числа в ряду 0 и 1.

Вот пример рекурсивной функции, которая генерирует ряд Фибоначчи:

function fibonacci(n) {
  if (n <= 1) {
    return n;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

В этой функции базовый случай — это когда n меньше или равно 1. Функция возвращает n, что равно 0 или 1. Рекурсивный случай — это когда n больше 1. Функция вызывает себя n - 1 и n - 2 в качестве аргументы и добавляет результаты.

Вот пример вызова функции fibonacci:

console.log(fibonacci(6)); // Output: 8

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

2. Бинарный поиск

Двоичный поиск — это распространенный алгоритм поиска определенного значения в отсортированном массиве. Алгоритм работает путем деления массива пополам и рекурсивного поиска в соответствующей половине до тех пор, пока элемент не будет найден или поиск не увенчается успехом.

function binarySearch(array, target, start, end) {
  if (start > end) {
    return -1;
  }
  
  let mid = Math.floor((start + end) / 2);
  
  if (array[mid] === target) {
    return mid;
  } else if (array[mid] < target) {
    return binarySearch(array, target, mid + 1, end);
  } else {
    return binarySearch(array, target, start, mid - 1);
  }
}

Если эта функция смутила вас, вы не одиноки. Вот подробное объяснение.

В этой функции базовым случаем является случай, когда start больше, чем end. Функция возвращает -1, что означает, что элемент не найден. Рекурсивный случай — это когда средний элемент в массиве не равен целевому элементу. Функция рекурсивно ищет в соответствующей половине массива в зависимости от того, является ли средний элемент меньше или больше целевого элемента.

Вот пример вызова функции binarySearch:

console.log(binarySearch(array, target, start, end)); // Output: 3

Этот код выведет 3, что является индексом целевого элемента в массиве.

Заключение

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