如何将树递归函数（或算法）转换为循环函数？

Question

我在 pascal （或 delphi ）中编写了一个递归树函数，但是当我运行它时出现“内存不足”消息。 我需要将这段代码中的计算递归函数转换为非递归函数，你能告诉我怎么做吗：

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.

Answer 1

递归函数使用堆栈来保存递归状态。

当转换为循环时，您实际上必须创建一个显式堆栈。您必须在循环内将元素推入堆栈或从堆栈中弹出元素。