递归 - 链表中倒数第 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);
}

我只想知道语句的执行顺序在递归中是如何发生的，即给定递归调用在第二个 if 条件之前，那么是否会检查第二个 if 条件？

Answer 1

I just want to know how order of execution of statements occur in recursion i.e given recursive call is before the second if condition , so will the second if condition be checked ?

是的，在递归调用 return 秒后，将检查第二个 if 条件。如果递归在到达链表末尾时终止，它将 return。这个概念对于理解递归是必不可少的。最特别的是，您必须了解每个函数调用（包括递归函数调用）都在其自己的上下文中执行，并且 return 控制在调用后立即恢复。它与执行流程相关联，而不是与调用的函数相关联——您不会通过递归调用函数而失去自己的位置。

Answer 2

函数printNthFromLast为链表中的每个节点递归调用自身。在 return 上，i 递增并且字段 data 仅在递归的第 n 个 return 中打印，因此对于第 n 个列表末尾的项目，最后计数为 1。 printNthFromEnd 将是一个更准确的名称。

这个函数仅作为一个测验很有趣：它更新全局不可访问状态，因此只能正确工作一次！它是 不可重入 行为的缩影：它不仅不应在不同的线程中使用，而且不应多次使用，句号。可以扩展此方法以通过另一个 static 变量从末尾获取第 n 个模式：

void getNthFromEnd(struct node *head, int n) {
    static int i = 0;
    static struct node *np = NULL;
    if (head != NULL) {
        getNthFromEnd(head->next, n);
        if (++i == n) np = head;
    }
    return np;
}

更好的选择是：

struct node *getNthFromEnd(struct node *head, int n) {
    struct node *np;

    for (np = head; n > 0; n--) {
        if (np == NULL) return NULL;
        np = np->next;
    }
    while (np != NULL) {
        head = head->next;
        np = np->next;
   }
    return head;
}

递归 - 链表中倒数第 n 个元素

Recursion - nth element from last in a linkedlist

c

recursion

linked-list