Цикл или рекурсия

[vadi]

Из текста учебника я понял, что код с использованием цикла эффективнее по сравнению с рекурсией. Но...

Я нашел в интернете функцию, которая из введенного в текстовое поле списка строк удаляет дубликаты. Мне нужна более специфическая задача, но очень похожая, и я решил взять за основу интернетный прототип. Он был реализован в виде рекурсии. Я сделал с циклом и он работает в разы быстрее, но меня терзают смутные сомнения. Ведь почему-то изначально программист (видимо более опытный чем я) сделал с рекурсией...

[foo]

Не парься. Любой рекурсивный алгоритм выразим итеративно. В языках без оптимизации хвостовой рекурсии (ЕМНИП, js к таковым относиться), рекурсия -- это жопа. Она память жрет, производительность падает. Не нужно рекурсивно ничего пейсать. Некоторые хомячки пишут рекурсивно, просто ради позерства, чтобы показать всему миру своим друзьям "в контакте", что они пишут в фапе-стайле.
Нутыпонел. (http://img4.wikia.nocookie.net/__cb20120320232551/glee/images/9/90/Neutral-feel-like-a-sir-clean-l.png)

[kobezzza]

ЕМНИП, js к таковым относиться
Все современные VM JS уже неплохо оптимизируют рекурсии (разумеется лишь частные случаи). Древней книжки Крокфорда начитался? Прежде чем включать умника нужно подумать (а лучше вообще не включать).

рекурсивно, просто ради позерства
Рекурсия - простое, очевидно и элегантное решение. Разумеется всё нужно юзать с умом.

[foo]

Все современные VM уже оптимизируют неплохо хвостовые рекурсии
Даже если так, надо еще писать в хвосто-рекурсивном стиле, а это гребаный адЪ. И даже с оптимизацией она сольет итерации.

Рекурсия простое, очевидно и элегантное решение.
Это очередной базворд. Приведи пример где это справедливо. Я чет не видел такого, если не считать задроченного до дыр факториала, да и то вопрос.

[kobezzza]

Это очередной базворд. Приведи пример где это справедливо. Я чет не видел такого, если не считать задроченного до дыр факториала, да и то вопрос.

Любой поиск в глубину, например удаление непустой папки. Только полный кретин будет "оптимизировать" это место переписывая 3 строчки рекурсия на 30 с циклом и искусственным стеком.

[foo]

(разумеется
И кстати, почему разумеется?

[kobezzza]

Даже если так, надо еще писать в хвосто-рекурсивном стиле, а это гребаный адЪ.
Писать надо так, чтобы работать с этим нормально было, а оптимизации оставь для компиляторов и специальных библиотек.

[foo]

3 строчки рекурсия на 30
Покажи пример. Нет такого даже близко.

[kobezzza]

Покажи пример. Нет такого даже близко.

Напиши паттерн "примесь" на рекурсии и без. Я писал оба варианта. Вариант на циклах больше раза в 2 и супер не очевидный.

Без рекурсии: https://github.com/kobezzza/Collection/blob/v4.0.0/lib/core/obj.jsn#L118

изучай.

***

Сколько лет ты пишешь код? 0.1? оно и видно, но зато в каждом треде всех учишь и рассказываешь сказки.

[foo]

Писать надо так, чтобы работать с этим нормально было, а оптимизации оставь для компиляторов и специальных библиотек.

kobezzza,
Ты уверен, что ты понимаешь о чем говоришь?

fact=function(n){if(n<2) return 1; return n*(fact(n-1))}

Это не хвосто-рекурсивный код. его соптимизировать невозможно.

[kobezzza]

И кстати, почему разумеется?
Очевидно ты никогда не раскручивал сложные рекурсии, мистер умник.

[foo]

в 2
В 2. А ты что написал? Это твой стиль? Я уже не первый раз замечаю. А в 2 -- этим можно пожертвовать ради ясности, это фигня.

[foo]

Очевидно
Очевидно, что компилятор с поддержкой хр обязан ее поддерживать, если она имеет место быть. Ты о чем то о своем разговариваешь.

[kobezzza]

foo, напиши реализация. Я дал тебе сссылку с пруфом, так что либо давай код, либо прекрати пиздеть и уёбывай.

[foo]

Ты несешь хуету. Пиздишь тут ты а не я. Ты может мастер по напейсанию js-сахарка, но в программировании ты дуб, и ты не понимаешь, что такое хвостовая рекурсия, ты слился в говно, и еще ебальник разеваешь при этом. А писать и перпеписывать я буду то что считаю нужным, есличо.

[kobezzza]

Очевидно, что компилятор с поддержкой хр обязан ее поддерживать, если она имеет место быть. Ты о чем то о своем разговариваешь.

Это в хаскеле так можно рассуждать. В супер-динамических языках всё гораздо сложнее. Я могу вставить какой нить new Function в тело функции и с большой долей вероятности никаких оптимизаций не будет.

[kobezzza]

foo слив засчитан.

[javascriptus-maximus-∆]

Ты несешь хуету. Пиздишь тут ты а не я. Ты может мастер по напейсанию js-сахарка, но в программировании ты дуб, и ты не понимаешь, что такое хвостовая рекурсия, ты слился в говно, и еще ебальник разеваешь при этом. А писать и перпеписывать я буду то что считаю нужным, есличо.

гнев одобряю

ибо нехуй форум портитьб!

[foo]

Это в хаскеле так можно рассуждать. В супер-динамических языках всё гораздо сложнее. Я могу вставить какой нить new Function в тело функции и с большой долей вероятности никаких оптимизаций не будет.
Ты опять о чем то о своем. То что компилятор не соптимизирует new Function, или эвал, это к делу отношения не имеет. И тут дело не в динамике. Любой компилятор, либо же интерпретатор scheme ОБЯЗАН поддерживать оптимизацию хвостовых вызовов, это заложено в стандарте.

[kobezzza]

Ты опять о чем то о своем.
Да ну? Может ты не в курсе, но вызов методов кодогенерации (особенно eval) может каскадо завалить всю оптимизацию всей функции.

Только я не понимаю, чёйт ты ушёл в оптмизации, если ты утверждаешь, что рекурсия не выразительная и не нужно поэтому её юзать.


removeFolder(cat) {
for (var i = 0; i < cat.length; i++) {
if (isFile(cat[i])) {
unlink(cat[i]);
} else {
removeFolder(cat[i]);
}
}

rmdir(cat);
}


Терь давай перепиши на циклы и докажи, что вариант на циклах очевиднее.

[foo]

с пруфом
И первоначально ты утверждал, что выигрышь в десятки раз. Так что пруфа я не вижу.

[foo]

for
Это че не цикл у тебя? Ты уж если за рекурсию, давай пример чисто рекурсивной реализации. А то я уж начинаю подозревать, что ты и не знаешь, что такое рекурсия. Ты ведь знаешь?

[kobezzza]

И первоначально ты утверждал, что выигрышь в десятки раз. Так что пруфа я не вижу.

Где я писал вообще что-то про выигрыш. Я писал что рекурсия очевиднее и проще и кода писать меньше и что не нужно оптимизировать то, что и так возможно будет с оптимизировано или в принципе нет смысла оптимизировать и дал ссылку с реализаций паттерна "примесь" на циклах, который хотя я сам его писал, но гораздо запутанней классической реализации на рекурсии.

[kobezzza]

Это че не цикл у тебя? Ты уж если за рекурсию, давай пример чисто рекурсивной реализации. А то я уж начинаю подозревать, что ты и не знаешь, что такое рекурсия. Ты ведь знаешь?
Ты обкурился?


removeFolder(cat) {
for (var i = 0; i < cat.length; i++) {
if (isFile(cat[i])) {
unlink(cat[i]);
} else {
removeFolder(cat[i]);
}
}

rmdir(cat);
}



removeFolder(cat[i]);


А это что? Я начинаю подозревать, что ты идиот (хотя стоп, я в этом уверен).

Ты уж если за рекурсию, давай пример чисто рекурсивной реализации.
Не нужно перевирать слова пытаясь казаться умным. Я говорил, что рекурсия очевидное и хорошее решение для многих задач, а не "нахуй циклы, хреначим всё на рекурсиях".

[foo]

Да ну
Ты понимаешь, что профит хвостовой рекурсии заключается в отсечении не нужных ветвей вычисления? Если ты напишешь внутри хвосто-рекурсивного вызова read-from-user-input твой код замерзнет вообще. Но это не отменяет отсечения лишних ветвей вычислений.

[foo]

А это что?
Да, это рекурсивная функция, которая внутри содержит цикл. Циклы в перемежку с рекурсией -- это некомильфо в фп, ты понял о чем я, не придуривайся.

зы код пока не смотрел.

[kobezzza]

Ты понимаешь, что профит хвостовой рекурсии заключается в отсечении не нужных ветвей вычисления?
Я говорю о конкретной реализации, а не о сферических конях в вакууме. eval как красная тряпка - вижу, значит ничего не делаю, никаких оптимизаций, тупое воспроизведение байт-кода "как есть".

[kobezzza]

Циклы в перемежку с рекурсией -- это некомильфо в фп
Всё с тобой ясно...

[foo]

kobezzza,
короче, не буду лить воды. Я проверил в ноде на следующем коде:


fs=require("fs")
write=function(){
fs.writeFileSync("./counter.txt", counter)
}

fu=function(){counter++; write(); fu()}
counter=0
fu()

path.js:163
resolvedTail = normalizeArray(resolvedTail.split(/[\\\/]+/).filter(f),
^
RangeError: Maximum call stack size exceeded

Эта функция 100% содержит хвосторекурсивный вызов. Если бы оптимизация была, этот код выполнялся бы бесконечно. Как видишь, никаких эвалов и прочих Function тут нет. Выполнение остановились на 25104
Попробуй на своей модной новейшей ноде, потом расскажешь. А пока я засчитываю тебе слив. В JS нет оптимизации хвостовой рекурсии.

[melky]

kobezzza,
Ты уверен, что ты понимаешь о чем говоришь?

fact=function(n){if(n<2) return 1; return n*(fact(n-1))}

Это не хвосто-рекурсивный код. его соптимизировать невозможно.
единственный кейс для кодогенерации и eval в JavaScript

невозможно.
я бы так не говорил :no:

[foo]

единственный кейс для кодогенерации и eval в JavaScript
Я не совсем понял. Вы о чем? зачем там эвал?я бы так не говорил
Ну а как?:) Я говорю конкретно про оптимизацию хвостовой рекурсии, а не оптимизацию в вакууме, а Вы о чем?

[melky]

можно попробовать перевести код функции к циклу через конструкцию с throw и try-catch

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

бредовый пример :) правда чутка мимо кассы

функция

function foo (from) {
return from ? foo ( document.body.innerHTML = --from ) : from;
}


вызываем

foo(1e6);


JSBIN ---> http://jsbin.com/rojeguze/1

и её взломанный вариант

function foo (from) {

function foo () {
throw arguments;
}

while (true) {

try {

// START
return from ? foo ( document.body.innerHTML = --from ) : from;
// END

} catch (e) {
from = e[0];
}

}

}


Осторожно! Firefox замерзает на несколько секунд.
JSBIN ---> http://jsbin.com/ridibaye/1

[kobezzza]

Эта функция 100% содержит хвосторекурсивный вызов. Если бы оптимизация была, этот код выполнялся бы бесконечно. Как видишь, никаких эвалов и прочих Function тут нет. Выполнение остановились на 25104
Попробуй на своей модной новейшей ноде, потом расскажешь. А пока я засчитываю тебе слив. В JS нет оптимизации хвостовой рекурсии.

Да, нет, но нет в том виде, как например в Lisp, т.е. полная замена хвостового вызова на цикл и поэтому у нас всегда есть ограничение в виде максимальной глубина стека вызова. Т.е. на уровне языка никаких стандартов про оптимизацию хвостовой рекурсии нет, НО

В современных VM JIT компиляторы неплохо оптимизируют такие виды рекурсий (уж не знаю что они там делают) и часто получается, что рекурсивная форма работает также быстро как и pure цикл, но ограничение стека по прежнему есть.

Пожалуй я не правильно выразил свою мысль, когда говорил про оптимизацию.

(Однако следует заметить, что настоящая оптимизация хвостовой рекурсии добавлена в стандарт ES6 и будет работать с флагом 'use strict')

***

Я всё жду когда ты мне дашь код паттерна "примесь" на циклах и докажешь, что та простыня кода очевиднее и лучше рекурсии :) Только не надо рассказывать, что "раз мы юзаем рекурсии, то не юзаем циклы". Для любой задачи поиска в глубину рекурсия самое простое, короткое и очевидное решение.

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

Пример я уже приводил:


removeFolder(cat) {
var dir = readdir(cat);

for (var i = 0; i < dir.length; i++) {
if (isFile(dir[i])) {
unlink(dir[i]);
} else {
removeFolder(dir[i]);
}
}

rmdir(cat);
}


Мне трудно представить ситуацию, когда количество вложенных папок приведёт к переполнению стека и придётся этот код переписывать :)

[foo]

дашь код паттерна "примесь" на циклах и докажешь, что та простыня кода очевиднее
Я, честно говоря, плохо язык знаю, я еще даже толком не въехал до конца в примеси, но я постараюсь, как время будет.
Я начал читать твой код, и, попутно вопрос возник. Ты там клонируешь объект

Collection.clone = function (obj) {
return JSON.parse(JSON.stringify(obj));
};

Но ведь он так не клонируется с прототипами? Нахрена так делать? Ведь это же "ненастоящее" клонирование, ты так объект не получишь. А в прототипах может быть 99% объекта, ты их выкидываешь. Это противоречит идеологии языка, имхо.

[kobezzza]

Collection.clone - это служебный метод для быстрого клонирования JSON валидных объектов, т.е. это частный случай и по сути хакерство, но работает для своих задач очень быстро.

Настоящие клонирования может сделать extend (https://github.com/kobezzza/Collection/blob/master/lib/core/obj.es6#L243) (тут уже я переписал на рекурсию с циклов, т.к. в последних VM профита уже не стало, а код стал реально понятнее и проще).


// Полное клонирование объекта a
var b = Collection.extend({deep: true, withProto: true, withAccessors: true}, {}, a)


Тут тебе и клонирование прототипов, аксессоров, штрихи, примеси и т.д.

[foo]

kobezzza,
А там у тебя let используется. Это же не часть стандарта насколько я понял? Зачем ты используешь let? чем тебя не устраивают var? Это же тоже самое, насколько я понимаю? Или есть разница?

[Erolast]

let - это часть ES6. И отличается он от var тем, что объявляет переменные с блочной областью видимости.

[kobezzza]

Вот для сравнения сейчас накалякал на коленке: функция удаления непустой папки (которая может содержать вложенные папки и т.д.)

С рекурсией: - 13 строк


function removeFolder(cat) {
var dir = readdir(cat);

for (var i = 0; i < dir.length; i++) {
if (isFile(dir[i])) {
unlink(dir[i]);
} else {
removeFolder(dir[i]);
}
}

rmdir(cat);
}


Без рекурсии: - 35 строк


function removeFolder(cat) {
var dir = readdir(cat),
stack = [];

for (var i = 0; i < dir.length; i++) {
if (isFile(dir[i])) {
unlink(dir[i]);

} else {
stack.push({
i: i,
dir: dir,
cat: cat
});

cat = dir[i];
dir = readdir(cat);
i = -1;

continue;
}

if (i === dir.length - 1 && stack.length) {
rmdir(cat);
var last = stack.pop();

cat = last.cat;
dir = last.dir;

i = last.i;
}
}

rmdir(cat);
}


Вариант на одних циклах в 2.5 раза больше, понять его сложнее и сложнее модифицировать.
Мне кажется это самоочевидно, я даже не понимаю о чём тут можно спорить.

Конечно, когда у нас хвостовая рекурсия, то её с оптимизировать можно проще, т.к. не нужно создавать стек, но это уже частный случай.

[kobezzza]

kobezzza,
А там у тебя let используется. Это же не часть стандарта насколько я понял? Зачем ты используешь let? чем тебя не устраивают var? Это же тоже самое, насколько я понимаю? Или есть разница?

Я пишу на новом стандарте ES6 и использую транслятор в ES5.
let - это переменная с блочной видимостью, а var с функциональной.


if (1) {
let a = 1;
}
a // a is not defined

[foo]

et - это переменная с блочной видимостью, а var с функциональной.

Нахрен надо язык усложнять. что трудно в функцию обернуть чтоли? И так язык в посмешище превратили. А тут и еще одна неоднозначность появляется. В большинстве языков, насколько я помню, лет -- это как раз таки лексическое замыкание. По идее, лет с вар логично было бы поменять. Цирк да и только:)

[Erolast]

Да, разрабы языка-то тупые, все программисты языка тупые, а ты один умный и знаешь как надо.

[foo]

разрабы языка
Разраб там один. То что сейчас делается, делается тупыми комитетчиками. Не думаю, что автор сэлфа с сишным синтаксисом, доволен тем, что его детище превращается в жабу.

[javascriptus-maximus-∆]

foo, ты согласен с тем шо можно обойтись без рекурсии и она на самом деле нафик не нужна ?