链表递归..为什么需要return语句？

Question

void add(llist *list, lnode *newNode){
    list->size++;
    addRecursion(&list->head, newNode);
}

lnode* addRecursion(lnode **node, lnode *newNode){
    if(*node == NULL){
        *node = newNode;
    }
    else{
        lnode *nextNode = (*node)->next;
        (*node)->next = addRecursion(&nextNode, newNode);

    }
    return *node;
}

这段代码工作正常..我在网上查看了代码并做了一些更改。但我仍然不明白为什么 addRecursion 函数必须有返回类型。我改变了功能，

void addRecursion(lnode **node, lnode *newNode){
        if(*node == NULL){
            *node = newNode;
        }
        else{
            lnode *nextNode = (*node)->next;
            addRecursion(&nextNode, newNode);

        }
    }

然后它不起作用..

Answer 1

它总是返回存储到 *node 中的值，并且在修改后的代码中它会丢失该值，因为递归调用传递本地临时值而不是实际需要放置该值的位置，然后在返回后进行存储。一个非常奇怪的结构。如果您只是删除该本地变量，则可以使 addRecursion 无效（并且更简单）：

void addRecursion(lnode **node, lnode *newNode){
    if(*node == NULL){
        *node = newNode;
    }else{
        addRecursion(&(*node)->next, newNode);
    }
}

Answer 2

将某些内容分配给 (*node)->next。我想，它指向列表的下一个节点。因此，如果没有该分配，列表不会转到要添加新节点的最后一个节点。递归可以用迭代代替。

Answer 3

因为该函数返回下一个节点的地址，这是算法中设置最终节点所需的。

Answer 4

随着递归的进行，它可能有助于可视化调用堆栈的增长/收缩。假设如下列表：

node1 -> node2 -> node3 -> null

然后 addRecursion 展开如下（伪代码）：

addRecursion(&node1, newNode)
    node1.next = addRecursion(&node2, newNode);
        node2.next = addRecursion(&node3, newNode);
            node3.next = addRecursion(null, newNode); // returns &newNode
            node3.next = &newNode;
        node2.next = &node3;
    node1.next = &node2;
// return value ignored

新节点被添加到末尾，并且链中的每个链接都被保留。

Answer 5

如果您对代码进行此调整，将 nextNode 的值重新分配回 (*node)->next ，因为您传递了该值，它也应该有效参考递归函数调用（因此在后来的递归调用期间对其进行了修改）：

void addRecursion(lnode **node, lnode *newNode)
{
    if(*node == NULL)
    {
        *node = newNode;
        return;
    }

    lnode *nextNode = (*node)->next;
    addRecursion(&nextNode, newNode);
    (*node)->next = nextNode; //Add this line to re-connect the link
}

克里斯上面的版本更干净一些，因为它取消了两个赋值，并且这样做还节省了堆栈上的一些空间，因为没有存储本地指针变量 nextNode 所必需的。