..Рекурсия

Нередко при написании сценариев WSH возникает задача так называемого “обхода дерева”. Что это значит? Фактически, это перебор всех элементов многомерного массива. Например, поиск файлов по маске в каталоге со всеми подкаталогами, является типичным представителем такого рода задач. То есть нам надо зайти в каталог, перебрать все находящиеся в нем файлы, затем зайти в его подкаталог(и), перебрать все файлы оттуда, и так до самого конца дерева файлов. Когда структура каталогов и подкаталогов нам не известна, решить эту задачу “в лоб”, просто указав их список для поиска, невозможно. В данном случае поможет такой замечательный инструмент, как рекурсия.

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

/********************************************
   Суммирование массивов с помощью рекурсии
*********************************************
   Создаем несколько массивов, пока одномерных 
********************************************/
var v1 = new Array(1,1,1,1,1,1,1,1);
var v2 = new Array(2,2,2,2,2,2,2,2);
var v3 = new Array(3,3,3,3,3,3,3,3);
/* Создаем двумерный массив */
var v = new Array(v1,v2,v3);
/* А вот это массив уже многомерный */
var vQ = new Array (v,v,v2,v3);
/* Цель создания таких массивов - имитация работы рекурсивных
алгоритмов. Классическая задача "Последовательный обход 
"дерева" решается легко и просто с помощью рекурсии */
var res = 0;

function Work(arg){
	/* Все переменные, которые участвуют 
	 в работе рекурсии, должны быть определены
	 только внутри этой функции !!!   */
	var i;
	/* Обязательно определяем условия
	 выхода из функции, иначе получим
	 вечный цикл */
	if((arg==null)||(arg.length==0)){
		return 0;
	}
	switch(typeof(arg)){ // Определяем тип объекта
		case "object": // Если это массив
			// Бежим по массиву
			for(i=0; i < arg.length; i++){
			/*******************************
			 !!! Вызываем рекурсивно функцию
			 Аргументом служит элемент массива
			 это м.б. массив массивов, 
			 массив, число
			*******************************/
				res = Work(arg[i]);  	
			}
			break;
		case "number": // Если аргумент - число
			res+=arg; // Просто суммируем
			break;
	}
	return res; // Возвращаем рузультат
}
/********************************
   Несколько вариантов подсчета
	- на одномерном массиве
	- на двумерном
	- на многомерном
********************************/
WScript.echo(Work(v1));
WScript.echo(Work(v));
WScript.echo(Work(vQ));

Рассмотрим более конкретную задачу – выберем все подкаталоги из какого-то каталога (при запуске сценария не стоит увлекаться и указывать каталог с большой вложенностью, иначе список всех подкаталогов просто не поместится на экране). Пример написан на VBScript.

Set objFSO = CreateObject("Scripting.FileSystemObject")
Set objParentFolder = objFSO.GetFolder("C:\WINNT")
Result = ""
ShowSubfolders objParentFolder

Sub ShowSubFolders(Folder)
   For Each Subfolder in Folder.SubFolders
	Set objSubFolder = objFSO.GetFolder(Subfolder.Path) 
	ShowSubFolders Subfolder
	Result = Result & Subfolder & CHR(10)
   Next
End Sub

WScript.Echo Result

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

©Измайлов Феликс

©Чеботарев Игорь

   Отправить статью как PDF