Skip to main content

Які задачі вирішує рекурсія

JavaScriptJunior~1 хв читання
Запропонувати правку

Рекурсія часто застосовується для розв'язання задач, де велику задачу можна природно розділити на підзадачі того самого типу. Ось найтиповіші приклади.

1. Математичні обчислення

  • Факторіал числа: n! = n * (n-1)!

  • Числа Фібоначчі: F(n) = F(n-1) + F(n-2)

  • Піднесення до степеня через розділення задачі:

    javascript
    function pow(x, n) { if (n === 0) return 1; return x * pow(x, n - 1); }

2. Обхід структур даних

  • Дерева (наприклад, DOM, файлова система):

    javascript
    function traverse(node) { console.log(node.value); node.children.forEach(traverse); }

  • Графи (DFS, BFS - часто реалізуються рекурсивно).

3. Робота з масивами

  • Сума елементів, пошук, фільтрація:

    javascript
    function sum(arr) { if (arr.length === 0) return 0; return arr[0] + sum(arr.slice(1)); }

4. Алгоритми "розділяй і володарюй"

  • Швидке сортування (QuickSort)
  • Сортування злиттям (MergeSort)
  • Бінарний пошук
  • Алгоритм Ханойської вежі

5. Обробка вкладених структур

  • Розгортання (flatten) масиву:

    javascript
    function flatten(arr) { return arr.reduce((acc, val) => acc.concat(Array.isArray(val) ? flatten(val) : val), []); }

6. Розв'язання логічних і комбінаторних задач

  • Перебір усіх комбінацій і перестановок;
  • Пошук шляху в лабіринті;
  • Розв'язання "зважених" задач типу рюкзака (knapsack).

Підсумок: Рекурсія застосовується всюди, де задачу можна виразити через простішу версію самої себе - особливо під час роботи з вкладеними, деревоподібними й подільними структурами даних.

Коротка відповідь

Для співбесіди
Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.

Запропонувати правку