Как рекурсию заменить максимально быстрым циклом
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, время: 12:58. |