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

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

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

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

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

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

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

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

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

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

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

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

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

Без рекурсии: https://github.com/kobezzza/Collecti...e/obj.jsn#L118

изучай.

***

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

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

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

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

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

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

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

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

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

гнев одобряю

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

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

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

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

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) {
    for (var i = 0; i < cat.length; i++) {
        if (isFile(cat[i])) {
            unlink(cat[i]);
        } else {
            removeFolder(cat[i]);
        }
    }

    rmdir(cat);
}

removeFolder(cat[i]);

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

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

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

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

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

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

Всё с тобой ясно...

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

единственный кейс для кодогенерации и eval в JavaScript

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

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

можно попробовать перевести код функции к циклу через конструкцию с 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

Да, нет, но нет в том виде, как например в 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);
}

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

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

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

Настоящие клонирования может сделать extend (тут уже я переписал на рекурсию с циклов, т.к. в последних VM профита уже не стало, а код стал реально понятнее и проще).

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

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

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

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

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

С рекурсией: - 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 раза больше, понять его сложнее и сложнее модифицировать.
Мне кажется это самоочевидно, я даже не понимаю о чём тут можно спорить.

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

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

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

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