What problems does recursion solve

Recursion is often used to solve problems where a large task can naturally be broken down into subtasks of the same type. Here are the most typical examples.

---

#1. Mathematical calculations

• Factorial of a number: n! = n * (n-1)!

• Fibonacci numbers: F(n) = F(n-1) + F(n-2)

• Exponentiation by splitting the task:

  javascript

  Copy

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

---

#2. Traversing data structures

• Trees (for example, the DOM, a file system):

  javascript

  Copy

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

• Graphs (DFS, BFS are often implemented recursively).

---

#3. Working with arrays

• Summing elements, searching, filtering:

  javascript

  Copy

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

---

#4. "Divide and conquer" algorithms

• QuickSort
• MergeSort
• Binary search
• The Tower of Hanoi algorithm

---

#5. Processing nested structures

• Flattening an array:

  javascript

  Copy

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

---

#6. Solving logical and combinatorial problems

• Enumerating all combinations and permutations;
• Finding a path in a maze;
• Solving "weighted" problems like the knapsack problem.

---

Summary: Recursion applies everywhere a task can be expressed through a simpler version of itself - especially when working with nested, tree-like, and divisible data structures.