Как правильно связывать ООП и рекурсию?

durka82

Если рассматривать рекурсивные алгоритмы, результатом которых является одно число (например, вычисление выражения со скобками) - там все просто - рекурсивная ф-я возвращает один результат - число.
А как быть, когда результат - некоторая структура данных, которая формируется в процессе работы рекурсии?
Например, если рассматривать алгоритм определения всех простых делителей числа, нужно ли, чтобы результатом рекуррентной функции было множество всех простых делителей, найденных для текущего делителя числа.
Или надо все таки формировать результат как параллельную рекурсии структуру данных?
Какой вариант правильнее? Или какие еще есть варианты?
Причем здесь ООП? Если писать эта на java/c++ - надо будет все это вписать в такой подход.
Как это лучше сделать?

Dasar

1. хранить данные на уровне объекта
2. переделать рекурсию в цикл, и хранить данные на уровне метода

durka82

1. хранить данные на уровне объекта
Какого конкретно?
2. переделать рекурсию в цикл
То есть обычная рекурсия и ооп - не совместимы?
хранить данные на уровне метода
Это как?

Julie16

Используй рекурсивный метод объекта, хранящего эти данные.

garikus



TYPE

    B = OBJECT (A)

        data: Data;

        PROCEDURE Rec (...);

        BEGIN

            ...

            self.data := ...

            ...

            Rec(...);

            ...

        END Rec;

    END;

garikus

То есть обычная рекурсия и ооп - не совместимы?
Методы - процедуры, ассоциированные с типом данных, и использование таких процедур не ограничивает использование рекурсивных алгоритмов.

Dasar

> Какого конкретно?
Вспомогательного.
> Это как?
в локальной переменной

durka82

То есть создавать объект результата, а рекурсивный вызов делать в виде метода этого объекта - так?

durka82

Это Оберон?
А можно пример на чем-нибудь более привычном (хотя мб я просто торможу и потом его пойму)7..

durka82

> Какого конкретно?
Вспомогательного.
Ты про объект результата?
> Это как?
в локальной переменной
Понял.

Dasar

> То есть создавать объект результата, а рекурсивный вызов делать в виде метода этого объекта - так?
так тоже можно, но лучше создавать временный объект на время работы рекурсии

Julie16

Чем же это лучше?

Dasar

логически стройнее

durka82

О каком временном объекте ты говоришь?
Что он должен делать?

Dasar

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


результат recurse(начальные данные)

{

   o = new ВспомогательныеОбъект(начальные данные);

  o.Recurse;

   return o.Result;

}

такое преобразование экономит память стека, а также время на копирование операндов

durka82

такое преобразование экономит память стека
Не очень понятно, за счет чего это происходит.
Да, параметры передавать не надо, зато при каждом вызове надо создавать ВспомогательныйОбъект.
Или это синглетон?
Кстати, какие-нибудь шаблоны на этот случай не предусмотрены случайно?

durka82

Жаль, интересно было бы посмотреть твой пример.

Dasar

> Не очень понятно, за счет чего это происходит
потому что нач. условия, и вспомогательные данные не пихаются в стек на каждой итерации рекурсии
> Да, параметры передавать не надо, зато при каждом вызове надо создавать ВспомогательныйОбъект.
на каком еще каждом вызове?

garikus

Вот пример обхода объектно-ориентированного дерева (в порядке in-order) на компонентном паскале:
MODULE TmpM;

	IMPORT TextMappers, TextModels, TextViews, Views;

	TYPE

		Node = POINTER TO RECORD

			left, right: Node;

			x: INTEGER

		END;

		Tree = RECORD

			root: Node

		END;

	PROCEDURE (VAR t: Tree) Fill, NEW;

	BEGIN

		NEW(t.root); t.root.x := 2;

		NEW(t.root.left); t.root.left.x := 3;

		NEW(t.root.left.left); t.root.left.left.x := 7;

		NEW(t.root.right); t.root.right.x := 5;

	END Fill;

	PROCEDURE (VAR t: Tree) Dump (VAR f: TextMappers.Formatter NEW;

		

		(* In-order *)

		PROCEDURE Rec (n: Node);

		BEGIN

			IF n # NIL THEN

				Rec(n.left);

				f.WriteInt(n.x);

				Rec(n.right)

			END

		END Rec;

		

	BEGIN

		Rec(t.root)

	END Dump;

	PROCEDURE Do*;

		VAR t: Tree;

                        f: TextMappers.Formatter;

			m: TextModels.Model;

			v: TextViews.View;

	BEGIN

		t.Fill;

		m := TextModels.dir.New; f.ConnectTo(m);

		t.Dump(f);

		v := TextViews.dir.New(m); Views.OpenView(v)

	END Do;

END TmpM.

После запуска TmpM.Do появляется окошко с текстом "7325"

f - это те самые данные.
На Java и C# должно быть аналогично.

durka82

Все таки я не понял, в чем смысл ВспомогательныеОбъект в твоем примере.
Ведь он является объектом результата - o.Result.
Так в чем его отличие от объекта результата?
Ведь вызов Recurse у ВспомогательныеОбъект и вызов "результат recurse(начальные данные)" - это разные вызовы?
И как ты передаешь измененные начальные данные в очередной вызов?

durka82

Спасибо, посмотрю

Dasar

рекурсивный обход дерева с возвращением линейного списка всех вершин, которые удовлетворяют условию
процедурный подход:


ITreeNode[] Browse(ITreeNode root, Filter filter)

{

   List<ITreeNode> nodes = new List<ITreeNode>

   foreach (ITreeNode child in root.Childs)

   {

       nodes.AddRange(Browse(child filter);

      if (filter(child

        nodes.Add(child);

   }

   return nodes.ToArray;

}

в итоге мы постоянно пихаем в стек filter, на каждой итерации создаем список, а также постоянно заняты слиянием списков
через вспомогательный объект


ITreeNode[] Browse(ITreeNode root, Filter filter)

{

    Browser browser =  new Browser(root, filter);

    browser.Browse(root);

    return browser.Nodes.ToArray;

}

class Browser

{

  public Browser(ITreeNode root, Filter filter)

  {

    this.root = root;

     this.filter = filter;

  }

  ITreeNode root;

  Filter filter;

   

   public void Browse(ITreeNode node)

   {

     foreach (ITreeNode child in root.Childs)

     {  

       Browse(child);   

      if (filter(child

        Nodes.Add(child);

        

     }

   }

   public List<ITreeNode> Nodes = new List<ITreeNode>

}

видно, что на каждой итерации нет передачи нач. условий (ссылки на filter вспомогательные данные/результат тоже не копируется.

Marinavo_0507

что-то во втором примере не видно рекурсивного вызова или его замены
за ОО-лоском потерялось главное

Dasar

sorry, исправил.
copy/cut/paste-ил - и за cut-ил лишнего.

Marinavo_0507

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

Dasar

> конкатенация списков делается вручную вместо вызова библиотечной функции
на практике, чистые списки редко используются - соответственно конкатенация списков может быть довольно длительной операцией.
> ну и в 2 раза длиннее стало по сравнению с процедурным примером
это единственный критерий?
в данном примере, всего на всего приведено замыкание исходного процедурного примера.
алгоритмы оптимизации ФЯ делают обычно все тоже самое, получая такой же результат.
Оставить комментарий
Имя или ник:
Комментарий: