Рекурсия связанного списка. Почему мне нужно возвращать оператор?

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

Он всегда возвращает значение, которое он хранит в * узле, и в вашем измененном коде он теряет это значение, так как рекурсивный вызов передает локальный темп, а не место, в котором он фактически должен поместить значение, а затем сохраняет его после него.возвращается.Очень странная конструкция.Вы можете сделать addRecursion недействительным (и более простым), если просто избавитесь от этой локальной переменной:

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

Answer 2

Поскольку функция возвращает адрес следующего узла, который требуется в вашем алгоритме для установки конечного узла.

Answer 3

Это может помочь визуализировать увеличение / уменьшение стека вызовов по мере продвижения рекурсии.Предположим, следующий список:

node1 -> node2 -> node3 -> null

Затем addRecursion разворачивается следующим образом (psuedocode):

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 4

Чтобы назначить что-то для (*node)->next.Это указывает на следующий узел списка, я полагаю.Таким образом, без этого назначения список не переходит к последнему узлу, к которому должен быть добавлен новый узел.Рекурсию можно заменить на итерацию.

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.