Знаете, че 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, което е 6-то число от редицата на Фибоначи.

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, което е индексът на целевия елемент в масива.

Заключение

Рекурсията не е лесна концепция, за която да се замислите. Но когато най-накрая получите този момент „оооооо“, повярвайте ми, допаминът, който ще се носи в мозъка ви, струва всичко. Продължавайте да учите.