Функциональное программирование с точки зрения EcmaScript. Рекурсия и её виды

[dom1n1k]

1. Термальное (встречается в тексте 4 раза, то есть не опечатка) или всё же терминальное?
2. Зачем реализовывать «итеративный» вариант через рекурсию?

[Alex_Shcherbackov]

Да, правильно терминальное, но я, увы, привык говорить термальное и это отразилось в статье.

Рекурсия может быть реализована через итеративный процесс, у данной реализации есть свои преимущества.

[hrie]

Про хвостовую рекурсию забыли рассказать )

Термальное условие

Разве не терминальное? Термальное — это же что-то курортное.

[Alex_Shcherbackov]

Да, правильно терминальное, но я, увы, привык говорить термальное и это отразилось в статье.

[chapuza]

Думаю, очевидно, что итеративный процесс потребляет меньше памяти.

Да, TCO делает это утверждение бессмысленным, если не ошибочным. В языках с TCO можно не задумываясь считать факториалы миллионов и (если есть нативная поддержка целых чисел любой длмны) — даже напечатать ответ.

[GlukKazan]

Совсем не задумываясь не получится. Рекурсия должна быть хвостовой.

[chapuza]

Я думал, первая буква дважды упомянутой аббревиатуры TCO как бы намекает на это :)

После первых трех шишек, любая рекурсия автоматически выходит из под пера хвостовой.

[GlukKazan]

Ну если вы посмотрите на код, прямо над той фразой которую прокомментировали у автора, то как раз и увидите ту самую хвостовую рекурсию:

которую автор называет итеративным процессом

const factorial = (n) => {
  const iter = (counter, acc) => {
    if (counter === 1) {
      return acc;
    }
    return iter(counter - 1, counter * acc);
  };

  return iter(n, 1);
};

в отличии:

от

const factorial = (n) => {
  if (n === 0) {
    return 1;
  }

  return n * factorial(n - 1);
}

Неплохо вышла (возможно автоматически). Не очень правда понятно, что вам в ней не понравилось.

[chapuza]

В JS нет TCO, так что код выше помрет на сто-с-чем-то итерации от переполнения стека.

[GlukKazan]

Ага, я знаю. А ещё я знаю, что не любую рекурсию можно выразить через хвостовую, так что с Фибоначчи можете не трудиться.

[chapuza]

Если вы думаете, что Фибоначчи не выразить через хвостовую рекурсию, то это не так.

defmodule Fib do
  def calc(count), do: calc(1, 1, count - 1)

  def calc(_p, acc, 0), do: acc
  def calc(p, acc, count), do: calc(acc, acc + p, count - 1)

  def test do
    Enum.map(1..20, &calc/1) 
  end
end
#⇒ [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 
#   377, 610, 987, 1597, 2584, 4181, 6765, 10946]

Elixir поддерживает TCO, поэтому:

1_000_000 |> Fib.calc() |> to_string() |> String.length()
#⇒ 208988

[GlukKazan]

Я не знаком с Elixir, но похоже понял вашу мысль. Да, о таком варианте я не подумал, но не хотите же вы сказать, что любую рекурсию можно выразить через хвостовую? Ваше утверждение:

любая рекурсия автоматически выходит из под пера хвостовой

выглядит несколько смелым.

[GlukKazan]

Ну и кстати, было бы интересно посмотреть на ваш вариант хвостовой рекурсии для чисел Фибоначчи. Вы ведь достаточно шишек набили, чтобы автоматически получилось?

[zesikx]

Код да и даже некоторые комментарии к нему копипаст с hexlet, хоть бы ссылку на источник оставляли.

[Alex_Shcherbackov]

Добрый день! Пользовался только теми материалам, которые процитировал. Наверняка, рекурсию объясняют на множестве разных курсов, т.к. тема это важная для программиста.

[kosles]

кажется кто-то прочитал начало первой главы sicp и решил натянуть это на js ;-)

[Alex_Shcherbackov]

Добрый день! Не думаю, что рекурсию изучают только в МИТе. «Натягивать это на js ;-)» нет необходимости, т.к. рекурсия заложена в сам язык.