recursion - 递归函数如何在具有堆栈概念的链表中工作？

Question

在这里，我给出了一个打印链表反向的代码。

fun1() 以相反的方式打印给定的链表。对于链表 1->2->3->4->5，fun1() 打印 5->4->3->2->1。

void fun1(struct node* head)
{
  if(head == NULL)
    return;

  fun1(head->next);
  printf("%d  ", head->data);
}

任何人都可以解释每次调用 fun1() 时堆栈帧是如何构建的吗？我预计链表的最后一个节点会打印出来。但我以相反的顺序获得链表。它没有使链表反向。它只是反向打印。我认为这是由于 Push/Pop 之类的堆栈操作。但具体我不知道。请借助图表中的逐步操作帮助我理解。

Answer 1

我不太确定您要达到的目标。您的代码准确地打印了它应该做什么。以下是符合您期望的代码段：

我预计链表的最后一个节点会打印出来。

void fun1(struct node* head)
{
  if(head == NULL)
     return;
  if(head->next == NULL)
   {
     printf("%d  ", head->data);
     return;
   }
  else
   fun1(head->next);
}

Answer 2

如果您向其提供列表 1->2：

1. head=1->2，head 不为空，以 2 重复（继续 5）
2. => head=2，head 不为 null，以 null 重复（继续 4）
3. => => head=null，head为null，返回
4. => 打印头-> 数据 "2" 并返回
5. 打印头数据“1”并返回

如果您要在打印语句再次出现之前移动它：

void fun1(struct node* head)
{
  if(head == NULL)
    return;

  printf("%d  ", head->data);
  fun1(head->next);
}

它会是这样的：

1. head=1->2，head 不为空，打印 head->data “1”，以 2 重复（继续 5）
2. => head=2，head 不为 null，打印 head->data "2"，以 null 重复（继续 4）
3. => => head=null，head为null，返回
4. => 返回
5. 返回

在这两种情况下，都会打印所有非空节点。要仅打印其中一个，您的代码必须将其与另一个区分开来，如下所示：

void print_last(struct node* n)
{
    if( n == NULL )
    {
        printf("empty list!");
    }        
    else if( n->next == NULL )
    {
        printf("%d", n->data);
    }
    else
    {
        print_last(n->next);  
    }
}

用你得到的相同列表 1->2 调用；

1. n=1->2, n != null 和 n->next != null，以 2 重复（继续 3）
2. => n=2，n != null 和 n == null。打印 n->data "2" 并返回
3. 返回

请注意，当找到最后一个元素时它不会递归，因此 n 为 null 的唯一方法是如果您尝试打印空链表 (NULL)。