Как рекурсию заменить максимально быстрым циклом

[Dmitriyff]

короче кури тему про графы и обход бинарных деревьев.

[megaupload]

Спасибо конечно, но мне кажется это тут не при чем, и я просто создам стек с переменными;

[Dmitriyff]

dom - это по сути бинарное дерево, код который я привел из разделов связанных с обходом бинарных деревьев. так что оно тут как раз при чем =-)

и я просто создам стек с переменными;

эм... не уловил к чему это, собствено пример который я привел как раз со стеком =-)

[kobezzza]

Рекурсия (правильная не как у тебя в первом случае ) циклом не опишется. Она для того и делается.
Потому как не известно не только число итераций, но и уровень вложения.

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

Любую рекурсию можно разложить в цикл. Общий принцип прост (хотя есть сложные рекурсии которые так просто не разложишь).

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

Как пример сложной рекурсии развёрнутой в цикл могу привести свою реализацию метода extend (как в jQuery, т.е. глубокое копирования произвольного количества аргументов произвольной глубины и структуры)

https://github.com/kobezzza/Collecti...re/obj.js#L151

[ksa]

Любую рекурсию можно разложить в цикл. Общий принцип прост (хотя есть сложные рекурсии которые так просто не разложишь).

Это как понять?

Рекурсию для того и используют, что цикл тут не применим... Поскольку даже не понятно сколько штук их будет.

[kobezzza]

Это как понять?

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

Рекурсию для того и используют, что цикл тут не применим... Поскольку даже не понятно сколько штук их будет.

Почитай мат часть что ли, как работает рекурсия программно на уровне компилятора или если тебе лень попробуй объяснить как работает код по ссылке что я привёл выше без рекурсии.

[ksa]

kobezzza, напиши мне цикличный алгоритм подсчета количества файлов в папках.

Т.е. есть корень диска... Там есть как файлы, так и папки... В каждой папке могут быть как файлы так и папки.
Сделай это без рекурсии, только циклами.

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

[ksa]

Ты написал что рекурсию нельзя описать с помощью цикла

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

[ksa]

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

Смысл сначала куда-то залезть рекурсивно... А потом работать с полученым цыклом?
При том утверждать, что де сделал все без рекурсии!

Мы создаём стек ручками ...

Это уже какой-то частный случай... А не общий подход к рекурси.
Или вся твоя "матчасть" к этому и сводится?

[kobezzza]

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

Я как не странно тоже.

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}}})));

Смысл сначала куда-то залезть рекурсивно... А потом работать с полученым цыклом?
Притом утверждать, что де сделал все без рекурсии!

Я писал, что мы руками создаём стек, и эмулируем рекурсию циклом, а смысл: нет проблемы переполнения стека и работает значительно шустрее, к примеру мой вариант extend от 2 до 8 раз быстрее рекурсивного (в зависимости от браузера).

Это уже какой-то частный случай... А не общий подход к рекурси.
Или вся твоя "матчасть" к этому и сводится?

Ты можешь бесконечно спорить на эту тему, но факт остаётся фактом. Любую рекурсию можно раскрыть так.