C语言 递归-链表中倒数第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

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

是，在递归调用返回后，将检查第二个if条件。它将返回，前提是递归在到达链表的末尾时终止。这个概念对于理解递归是必不可少的。最特别的是，您必须理解每个函数调用，包括递归函数调用，都在其自己的上下文中执行，并且在调用结束后立即恢复控制。它与执行流程相关联，而不是与被调用的函数相关联——你不会因为递归地调用函数而丢失位置。

Answer 2

函数printNthFromLast对链表中的每个节点递归地调用自己。返回时，i被加1，字段data只在递归返回的n返回时被打印，因此对于列表末尾的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;
}