使用递归从末尾开始的第 n 个节点（链表）

Question

任何人都可以解释这实际上是如何工作的。我无法理解递归，当我们递归地到达链表的末尾后会发生什么，以及展开是如何与操作一起发生的（增量和条件检查）？

void printNthFromLast(struct node* head, int n) 
{
static int i = 0;
if(head == NULL)
   return;
printNthFromLast(head->next, n);
if(++i == n)
   printf("%d", head->data);
}

Answer 1

在我看来，这是一个非常糟糕的功能，但我会尝试解释我的看法。

基本上，您是将多个递归函数压入堆栈，直到遇到基本情况，但是每次您只弹出大约一半的函数，其余的留在下一个函数之后完成。当您遇到基本情况时，不再发生递归，您必须返回堆栈，弹出每个函数，直到您到达父函数，它会完成，您就完成了。

Answer 2

如果传递给它的结构节点*为 NULL，则函数 returns。如果链表有零个节点或者我们已经到达链表的末尾，就会发生这种情况。

if(head == NULL)
    return;

否则，函数的每个实例都将在此行等待 'child' 到 return:

printNthFromLast(head->next, n);

在我们到达列表末尾之前不进行打印。一旦我们到达列表的末尾，最终调用的函数将在 if 语句上 return 因为 head == NULL，因为我们在末尾。

函数的每个实例现在将继续执行这些行（一旦它 'child' 已 returned）：

if(++i == n)
    printf("%d", head->data);

基本上是从后面数的。每个实例将 i 递增 1，然后检查它是否等于我们提供的数字 n。如果是，它会打印数据。否则，它只是结束并且 'parent' 有机会执行这些行。

编辑： 这确实是一种非常糟糕的做你正在做的事情的方法。如果列表相当大，您的程序可能运行超出堆栈内存。你应该通过迭代来做到这一点。

使用递归从末尾开始的第 n 个节点（链表）

nth node from the end(Linked List) using recursion

c

recursion

linked-list