Шаг 1

Посмотрим на ещё одну классическую и простую для рекурсивного решения задачу: функция для получения числа из последовательности Фибоначчи по индексу. Первое её число — 0, второе — 1, а каждое последующее — сумма двух предыдущих. Если вы ещё не решали такую задачу — попробуйте сами найти базовый и рекурсивный случай для этой функции.

import {test} from "./tester"

/*
Примеры:
fibonacci(1) // 0
fibonacci(2) // 1
fibonacci(13) // 144
*/


function fibonacci(index) {
  return 0;
}


test(fibonacci(1), 0)
test(fibonacci(2), 1)
test(fibonacci(13), 144)

Шаг 2

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

import {test} from "./tester"

/*
Примеры:
fibonacci(1) // 0
fibonacci(2) // 1
fibonacci(13) // 144
*/


function fibonacci(index) {
  if (index === 1) {
    return 0;
  }

  if (index === 2) {
    return 1;
  }
}


test(fibonacci(1), 0)
test(fibonacci(2), 1)
test(fibonacci(13), 144)

Шаг 3

А в рекурсивном случае мы будем пытаться прийти к базовым — вызывать ту же функцию, но понижая индексы у её аргументов.

import {test} from "./tester"

/*
Примеры:
fibonacci(1) // 0
fibonacci(2) // 1
fibonacci(13) // 144
*/


function fibonacci(index) {
  if (index === 1) {
    return 0;
  }

  if (index === 2) {
    return 1;
  }

  return fibonacci(index - 1) + fibonacci(index - 2);
}


test(fibonacci(1), 0)
test(fibonacci(2), 1)
test(fibonacci(13), 144)

Шаг 4

И ещё добавим обработку некорректных входных данных. Как видно на этих двух примерах, рекурсия — довольно простая для использования концепция, нужно лишь научиться сводить «сложные» задачи к их самым простым случаям. Конечно, обе реализации можно написать множеством других более оптимальных по времени и памяти способов, но эти — самые простые для восприятия и написания. Как оптимизировать решение задач через рекурсию мы узнаем чуть позже — в разделе про стек (хотя, казалось бы, при чём тут стек).

  import {test} from "./tester"

/*
Примеры:
fibonacci(1) // 0
fibonacci(2) // 1
fibonacci(13) // 144
*/


function fibonacci(index) {
  if (index < 1 || !Number.isInteger(index)) {
    throw new Error("Индекс должен быть целым числом больше или равным единице!");
  }

  if (index === 1) {
    return 0;
  }

  if (index === 2) {
    return 1;
  }

  return fibonacci(index - 1) + fibonacci(index - 2);
}


test(fibonacci(1), 0)
test(fibonacci(2), 1)
test(fibonacci(13), 144)

File tester.js

const results = document.getElementById('results')

export function test(left, right) {
  const result = document.createElement('li');

  if (left === right) {
    result.innerHTML = "Тест пройден!";
    result.style.color = "green";
  } else {
    result.innerHTML = `Тест не пройден! ${left} не равно ${right}`;
    result.style.color = "red";
  }

  results.appendChild(result);
}