Преобразование рекурсивной функции дерева в циклическую

Delphi , Синтаксис , Деревья

Заголовок: в Pascal/Delphi

В процессе программирования на Pascal/Delphi может возникнуть ситуация, когда рекурсивная функция, работающая с деревом, вызывает переполнение стека и сообщение об ошибке "Out of Memory". В этом случае необходимо преобразовать рекурсивную функцию в циклическую, чтобы избежать переполнения стека.

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

Исходный код рекурсивной функции:

program testing(input, output);
type
  ptr = ^tr;
  tr = record
    age: byte;
    left, right: ptr;
  end;

var
  topper: ptr;
  total, day: longint;

procedure mycreate(var t: ptr);
var
  temp: ptr;
begin
  new(temp);
  temp^.age := 1;
  temp^.left := nil;
  temp^.right := nil;
  t := temp;
end;

procedure gooneday(var t: ptr);
begin
  if t^.age <> 5 then
  begin
    if t^.age = 2 then
      mycreate(t^.left)
    else if t^.age = 3 then
      mycreate(t^.right);

    t^.age := t^.age + 1;
    total := total + 1;
  end;
end;

procedure calculate(var crnt: ptr);
begin
  if crnt <> nil then
  begin
    gooneday(crnt);
    calculate(crnt^.left);
    calculate(crnt^.right);
  end;
end;

begin
  total := 0;
  mycreate(topper);
  day := 0;

  while total < 1000000000000 do
  begin
    total := 0;
    day := day + 1;
    calculate(topper);
  end;

  writeln(day);
  writeln(total);
end.

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

Пример циклической функции:

program testing(input, output);
type
  ptr = ^tr;
  tr = record
    age: byte;
    left, right: ptr;
  end;

var
  topper: ptr;
  total, day: longint;
  stack: array of ptr;
  top: integer;

procedure mycreate(var t: ptr);
var
  temp: ptr;
begin
  new(temp);
  temp^.age := 1;
  temp^.left := nil;
  temp^.right := nil;
  t := temp;
end;

procedure gooneday(var t: ptr);
begin
  if t^.age <> 5 then
  begin
    if t^.age = 2 then
      mycreate(t^.left)
    else if t^.age = 3 then
      mycreate(t^.right);

    t^.age := t^.age + 1;
    total := total + 1;
  end;
end;

procedure push(var t: ptr);
begin
  SetLength(stack, Length(stack) + 1);
  stack[Length(stack) - 1] := t;
end;

procedure pop(var t: ptr);
begin
  t := stack[Length(stack) - 1];
  SetLength(stack, Length(stack) - 1);
end;

procedure calculate(var crnt: ptr);
begin
  top := 0;
  push(crnt);

  while top > 0 do
  begin
    pop(crnt);
    gooneday(crnt);

    if crnt^.right <> nil then
      push(crnt^.right);

    if crnt^.left <> nil then
      push(crnt^.left);
  end;
end;

begin
  total := 0;
  mycreate(topper);
  day := 0;

  while total < 1000000000000 do
  begin
    total := 0;
    day := day + 1;
    calculate(topper);
  end;

  writeln(day);
  writeln(total);
end.

В циклической версии функции мы используем динамический массив

Создано по материалам из источника по ссылке.

Приведен пример преобразования рекурсивной функции, работающей с деревом, в циклическую версию на языке программирования Pascal/Delphi, чтобы избежать переполнения стека.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Деревья ::