更好地理解链表中的递归

Question

我想更深入地理解递归，而不仅仅是直观地理解。我知道这个概念，我知道如何递归地求解阶乘或斐波那契数列。但是我似乎无法很好地想象递归使用链表时到底发生了什么。

更具体地说，我正在努力理解以下算法：

（它在链表中查找最大值。它通过从第二个元素开始递归搜索最大值来实现。然后将其与第一个元素和 returns 较高的元素进行比较。）

 function MaxRec (inRefBegin : tRefList) : tRefList;
  { returns recursively a pointer to the max element in a list }

    var
    rekMax : tRefList; { variable to point to the recursive maximum 
                          starting from second element }
    begin
      if inRefBegin = nil then { Base Case, recursion stops }
        MaxRec := nil
      else
      begin
        rekMax := MaxRec (inRefBegin^.next); 
        if rekMax = nil then
          MaxRec := inRefBegin
        else
          if inRefBegin^.info < rekMax^.info then
            MaxRec := rekMax
          else
            MaxRec := inRefBegin
      end { if }
    end; { MaxRec }

我确实明白理论上应该发生什么。我很难一步一步地想象它。每个堆栈级别会发生什么？我不明白的是这一行如何：rekMax := MaxRec (inRefBegin^.next) 可以找到最大值....它只调用带有指向下一项的指针的函数但不比较任何值....或者我比较每次调用函数的时间??

我的思考过程是这样的：假设我有一个这样的链表：

5 => 7 => 10 => 3 => 2 => nil

函数被调用并且不为零（（保存到堆栈））
函数被调用并且不为零（（保存到堆栈））
函数被调用并且不为零（（保存到堆栈））
函数被调用并且不为零（（保存到堆栈））
函数被调用并且不为零（（保存到堆栈））
递归停止
现在发生了什么？我是否将每个函数与第一个元素进行比较？或者这是我已经拥有递归最大值的地方？ s.o 可以形象化吗？

非常感谢您的每一次帮助。我知道这个主题在网上有大量资源，相信我，我已经阅读过它们。但是我仍然不清楚每个级别到底发生了什么。

Answer 1

7) Now what happens? Do I compare in each function with the first element? Or is this the point where I already have my recursive max? Can s.o visualize this?

在 7) 递归停止，因为您已到达列表末尾，因此返回 nil。然后您继续之前的调用，其中 MaxRec 的结果现在为 nil，因此最后一部分的最大值是当前的 inRefBegin 值（同样，因为返回了 nil）。

对于其他层次，在递归之外，将当前节点中的值与递归调用返回的值进行比较，保留最大的一个，直到最后剩下最大的整个列表的节点。

有帮助吗？

更好地理解链表中的递归

Understanding recursion better in linked lists

recursion

pascal

linked-list

list