Шаг 1

Мы уже видели бинарный поиск без рекурсии (в разделе про поиск) и с рекурсией (в разделе про рекурсию). На самом деле, каждое решение задачи рекурсией можно переписать на циклы, и наоборот. Чтобы максимально упростить демонстрацию, посмотрим на ещё одну рекурсивную функцию, которую мы уже видели (хоть она и не очень интересная с точки зрения логики) — функцию для вычисления последовательности Фибоначчи. Здесь мы можем наглядно посмотреть на то, сколько вызовов функций произошло, а на каждый из них выделялась память!

import {benchmark} from "./benchmarker";
import {logCall, printLogs} from "./logger"

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


function fibonacci(index) {
  logCall(index);

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

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

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

benchmark(() => fibonacci(20), 'fibonacci(20)');
printLogs();

Шаг 2

Этот код лишён главного недостатка рекурсии: стека вызовов. А значит, мы можем вызывать его вообще с любыми аргументами и не бояться упереться в максимальное количество подвызовов. Однако и читается он сложнее: вместо репрезентативного «текущее — сумма двух предыдущих» у нас появляются какие-то вспомогательные переменные, в логике обновления которых надо разбираться. Конечно, из-за простоты примера это не очень усложняет задачу. Но потому этот пример и был выбран: чтобы не переусложнять логику для демонстрации концепта. Главный вывод из этого демо: если код чуть сложнее по асимптотике и расходам памяти, но при этом легче для поддержки — используйте его. Он хоть и потратит немного времени вашего пользователя, но зато сэкономит время и нервы вам, если придётся погружать в него нового члена команды или себя самого через несколько месяцев.

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

import {benchmark} from "./benchmarker";


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

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

  // Переменные для хранения предыдущих двух чисел
  let grandParent = 0;
  let parent = 1;
  let current;

  for (let i = 3; i <= index; i++) {
    current = grandParent + parent;
    grandParent = parent;
    parent = current;
  }

  return parent;
}

benchmark(() => fibonacci(100), 'fibonacci(100)');

Шаг 3

А ещё в этом конкретном случае мы уменьшаем сложность алгоритма. В рекурсивном случае она была θ(1.6ⁿ) (почитать почему можно здесь), а в итеративном — всего O(n)!

import {benchmark} from "./benchmarker";

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


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

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

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

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

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

  // Переменные для хранения предыдущих двух чисел
  let grandParent = 0;
  let parent = 1;
  let current;

  for (let i = 3; i <= index; i++) {
    current = grandParent + parent;
    grandParent = parent;
    parent = current;
  }

  return parent;
}


benchmark(() => recursiveFibonacci(42), "recursiveFibonacci");
benchmark(() => iterativeFibonacci(42), "iterativeFibonacci");

File benchmarker.js

  const results = document.getElementById('results')

export function benchmark(callback, name) {
  const start = performance.now();

  const result = callback();

  const end = performance.now();

  const time = (end - start) / 1000;

  log(`${name} вернула ${result} за ${time.toFixed(5)} секунд`);
}

function log(message) {
  const result = document.createElement('li');

  result.innerHTML = message;

  results.appendChild(result);
}

File logger.js

const results = document.getElementById('results');

const logs = [];

export function logCall(argument) {
  const result = document.createElement('li');

  result.innerHTML = `fibonacci(${argument})`;

  logs.push(result);
}

export function printLogs() {
  const list = document.createElement('ol');

  logs.forEach(log => list.appendChild(log));

  results.appendChild(list);
}