Как рекурсию заменить максимально быстрым циклом
function ololo(q) { if(q>5) return; alert(q); ololo(q+1); } ololo(1) |
Вот это же не правильный вариант?
var stark = []; stark.push(1); while(stark.length){ var value = stark[stark.length-1]; if(value>5){ stark.pop(); break; }else{ alert(value); stark.push(value+1); } } |
Как я понимаю все переменные и параметры которые использует функция нужно запихать в стек?
|
function ololo(a,b) { for(var i=1; i<b+1; i++){alert(i);} } ololo(1,5); |
Deff, спасибо; Вы гений; Ваш пример превосходит мой в разы; А теперь сделайте то же самое с этим:
alertHTML( document.body ) function alertHTML(context){ alert(this.innerHTML); for ( var i = 0; context.childNodes.lenght; i++ ) { alertHTML(context.childNodes[i]) } } |
если вас порядок нод не волнует
самый быстрый так alertHTML(document.body); function alertHTML(context) { var nodes = context.childNodes, i = nodes.length; while (i--) alert(nodes[i]); } |
Dmitriyff,
Но ведь я создал эту тему для разбора способов развертывания рекурсии в циклы а не для какого-то конкретного решения проблемы; А Ваш вариант вообще, мягко говоря, не рекурсия; |
оу, сорри... не усмотрел =-))), сейчас придумаем
|
Цитата:
Потому как не известно не только число итераций, но и уровень вложения. Возможно некие частные слочаи, где как раз возможно определить что-то конечное, и можно будет "развернуть" в циклы... Но "общего" решения не будет. |
как-то так
var f = function(nodes) { var node, stack = []; stack.push(nodes) while (stack.length) { node = stack.pop(); if (node.childNodes.length) { var i = node.childNodes.length; while(i--) stack.push(node.childNodes[i]); } else { console.log(node); } } } |
короче кури тему про графы и обход бинарных деревьев.
|
Спасибо конечно, но мне кажется это тут не при чем, и я просто создам стек с переменными;
|
dom - это по сути бинарное дерево, код который я привел из разделов связанных с обходом бинарных деревьев. так что оно тут как раз при чем =-)
Цитата:
|
Цитата:
Мы создаём стек ручками, как массив и на каждый уровень вложенности пушим туда объект с текущем состоянием переменных, затем локальные переменные переопределяем и продолжаем алгоритм до тех пор пока рекурсия не закончится и тогда мы начинаем "всплытие", т.е. итеративно разворачиваем полученный массив и делаем на каждой итерации pop (т.е. срезаем крайне правый элемент). Как пример сложной рекурсии развёрнутой в цикл могу привести свою реализацию метода extend (как в jQuery, т.е. глубокое копирования произвольного количества аргументов произвольной глубины и структуры) https://github.com/kobezzza/Collecti...re/obj.js#L151 |
Цитата:
Рекурсию для того и используют, что цикл тут не применим... Поскольку даже не понятно сколько штук их будет. |
Цитата:
Цитата:
|
kobezzza, напиши мне цикличный алгоритм подсчета количества файлов в папках.
Т.е. есть корень диска... Там есть как файлы, так и папки... В каждой папке могут быть как файлы так и папки. Сделай это без рекурсии, только циклами. Причем все, что у тебя есть в инструментарии - показать содержимое папки, в том числе и корневой. |
Цитата:
Т.е. когда рекурсивный подход применяется как раз из-за невозможности применения циклов. |
Цитата:
При том утверждать, что де сделал все без рекурсии! :D Цитата:
Или вся твоя "матчасть" к этому и сводится? |
Цитата:
function extend(deep, target, var_args) { deep = deep || false; target = target || {}; var aLength = arguments.length, aEl, key, src, copy, clone, copyIsArray, i = 1, j, stack = [], level, last, lastEl; // Внешний цикл по расширяющим аргументам while (++i < aLength) { if ((aEl = arguments[i])) { // Цикл для эмуляции рекурсии while (aEl) { level = []; // Цикл по свойствам объекта for (key in aEl) { src = target[key]; copy = aEl[key]; // Защита от бесконечного копирования if (target === copy) { continue; } // Рекурсивное копирование свойств // (рекурсия развёрнута) if ( deep && copy && ((copyIsArray = Array.isArray(copy)) || typeof copy === 'object') ) { // Если копируемое свойство - массив if (copyIsArray) { copyIsArray = false; clone = src && Array.isArray(src) ? src : []; // Если копируемое свойство - объект } else { clone = src && typeof src === 'object' ? src : {}; } // Запоминаем вложенность, чтобы в дальнейшем к ней вернуться level.push({ target: target, clone: clone, aEl: aEl, copy: copy, key: key }); } else { target[key] = copy; } } // Если на уровне имеются вложенности, // то добавляем новый уровень в стек и // проиводим сдвиг в крайне правый элемент нового уровня if ((last = level.length)) { stack.push(level); last = level[last - 1]; // Ставим флаг, что элемент учавствует в обходе last['__COLLECTION_TMP__'] = true; // Устанавливаем новую точку отсчёта target = last.clone; aEl = last.copy; // На уровне нет вложенностей } else if ((last = stack.length)) { j = stack.length; while (j--) { lastEl = stack[j][stack[j].length - 1]; // Если звено не имеет детей и уже было использовано, // то удаляем крайне правый элемент и сдвигаем позицию обхода if (lastEl['__COLLECTION_TMP__'] && !stack[j + 1]) { lastEl.target[lastEl.key] = target; target = lastEl.target; aEl = lastEl.aEl; stack[j].pop(); // В звене не осталось элементов, // значит его можно удалить if (!stack[j].length) { stack.pop(); } // Если первое условие не верно, // значит продолжать цикл нет смысла } else { break; } } // Устанавливаем новую позицию обхода if ((last = stack.length)) { last = stack[last - 1]; lastEl = last[last.length - 1]; lastEl['__COLLECTION_TMP__'] = true; target = lastEl.clone; aEl = lastEl.copy; } } // Операция закончена if (!stack.length && !level.length) { break; } } } } return target; }; alert(JSON.stringify(extend(true, {}, {a: {b: 1}, c: {e: 2}}, {a: {b: {e: 2}}}))); Цитата:
Цитата:
|
kobezzza, еще раз повторюсь... Если задачка раскладывается на конечное число циклов и этого хватает для решения проблемы в общем виде - это не "рекурсивная задачка".
Если её кто-то решеет рекурсивно - это его проблема и ответственность. :D |
Цитата:
Цитата:
http://ru.wikipedia.org/wiki/%D0%A0%...81%D0%B8%D1%8F Цитата:
|
ksa,
Какой ты упрямый, прям как я :). Я часто пишу сначала на рекурсии, а затем переписываю на циклы, т.к. Цитата:
Цитата:
|
Цитата:
|
Цитата:
kobezzza, если все "так просто", почему движок не делает это за нас? |
Цитата:
И ещё как мне кажется проблема в том, что такую оптимизацию легко делать в функциональных языках, т.к. функция никак не может влиять на внешний контекст, а JS как известно процедурный и внутри функции могут спокойно переопределяться внешние и глобальные переменные, одним словом вызов функции с одинаковыми параметрами не гарантирует одинаковый результат, поэтому JIT компилятору JS трудно сделать универсальную замену (от сюда кстати также растут проблемы с инлайнингом функции). |
Цитата:
Сам так же уже придумал как с папками разобраться в один цикл, но с 2-мя табличками... Цитата:
Просто в моём случае все делается с базами данных и там я не получу никакого ускорения с другим подходом... Т.к. меня начнут тормозить операции с данными в таблицах. Поскольку одной оперативной памятью там не обойдешся... От этого и "плясал". Цитата:
И естественно много приобрёл благодаря вам. :thanks: Поскольку просто с задачками "из опереативной памяти" дело имел мало... |
Все идет по плану; Нубы вновь схлеснулись с отцами в поисках установления истины любую ли рекурсию можно заменить циклом?
Ответ конечно очевиден - любую, ибо вызов функций javascript это и есть цикл выполнения синтаксического дерева; Но нубы то этого не знают; Ееееекселент; Цитата:
ksa, ой кому-то припекло)) kobezzza, красава) все верно описал) |
Пасоны, напишИте регулярку для разворачивания рекурсии в цикл)
|
Цитата:
Диспут или обсуждение какой-либо проблемы - обычное дело. |
Да, но кому-то припекло)))
|
Часовой пояс GMT +3, время: 02:48. |