Suggest an edit

Improve this article

Refine the answer for “What problems does recursion solve”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

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
  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
  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
  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
  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**.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts237 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.