C - linked list reverse recursively: why use double pointer?

I am unclear why I have to use... first = Head

Actually, the first variable isn't needed in this code at all. It is just a copy of Head, so to simplify you can just replace the variable with Head. Everything will work the same without it:

if (Head == NULL)
  return;

if (Head->next == NULL) {
  *headpointer = Head;
  return;
}

Reverse(Head->next, headpointer);

Head->next->next = Head;
Head->next = NULL;

I am unclear why I have to use... *headpointer = Head

The Head variable is the pointer to the head of the list you want to reverse, and the function stores the head of the newly reversed list into *headpointer. It does this because Head is just a copy of the pointer that was passed in to the Reverse() function, so updating its value won't change the original pointer; that's why a separate double pointer variable is used.

why can't I just use Head = first?

Head is a copy of the pointer that was passed to the function. Updating the Head pointer will not update the original list pointer that you passed in. Also, as I said before, Head is the same as first, so an assignment like that does nothing.

Also, if first = Head line in front of the recursive function call Reverse(first->next, headpointer), don't the first->next value also equal to Head which points to the first node?

first->next (or Head->next) is just the next node in the list. The purpose of the function call is to reverse the rest of the list first, and then place Head (or first) at the end of the list (which is what the last two lines do).

Let's consider the function signature was like this:

void Reverse(struct Node* Head, struct Node* headpointer) {

And you call it like this

Reverse(myList);

myList is just an address to a Node, for example 0x1234. So it's equivalent to do:

Reverse(0x1234);

The address is copied to a new variable headpointer. When we modify headpointer we are modifying a local variable, not the myList we passed.

It's like if we did this:

struct Node* myList = 0x1234;
struct Node* headpointer = myList;
headpointer = 0xABCD;
// at this point myList is still 0x1234

So after the function returns, myList is still equal to 0x1234. That's not what we want because is should now point to the last node.

So how do we allow, the function to modify myList? We have to tell the function "hey, here's the address where you have to write to".

In C, in order to take the address of something we use the '&' operator:

Reverse(&myList);

And we must change the signature of the function accordingly:

void Reverse(struct Node* Head, struct Node** headpointer) {

Now headpointer is an address to an address to a Node. Or, as we say in C, a pointer to a pointer to a Node.

Here's a final example that can help understand.

struct Node* myList = 0x1234;
struct Node** headpointer = &myList; // now headpointer points to myList
*headpointer = 0xABCD;
// at this point myList is still 0xABCD
// we haven't changed headpointer, but the thing headpointer is pointing to!

It is necessary to be able to return the updated head node, but this could be done with a return value in lieu of using a double pointer.

Also, I believe that the function needs to be passed a pointer to the previous node so it can set that as the new next pointer.

So, I think your function would need three arguments (e.g.) cur, prev, headpointer.

If we return the head pointer, we can reduce this to two.

Here's a version that does that.

I've tried to annotate it as much as possible. I've added debug printf and some cross checking [which I used to debug it myself].

If you need to have a double pointer, this example could be adapted without too much trouble.

// revlist -- reverse singly linked list recursively

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    struct node *next;
    int data;
#ifdef CHECK
    int visited;                    // 1=node visited (check for looped list)
#endif
} Node;

#ifdef DEBUG
int dbglvl;                         // nesting level -- debug only
#endif

int
prt(Node *node)
{
    int data;

    if (node != NULL)
        data = node->data;
    else
        data = -1;

    return data;
}

#ifdef DEBUG
#define dbgprt(_fmt ...) \
    do { \
        printf("DBG/%d: ",dbglvl); \
        printf(_fmt); \
    } while (0)
#else
#define dbgprt(_fmt ...) \
    do { } while (0)
#endif

// reverse -- recursively reverse list
// RETURNS: pointer to head of reversed list
Node *
reverse(Node *cur,Node *prev)
// cur -- pointer to current node
// prev -- pointer to previous node
{
    Node *next;
    Node *head = NULL;

    do {
        // empty list
        if (cur == NULL)
            break;

        next = cur->next;

        dbgprt("BEG cur=%d prev=%d next=%d\n",
            prt(cur),prt(prev),prt(next));

        // at end of list -- set new head from tail node
        if (next == NULL) {
            head = cur;
            head->next = prev;
            dbgprt("SETHEAD head=%d head->next=%d\n",
                prt(head),prt(head->next));
            break;
        }

#ifdef DEBUG
        ++dbglvl;
#endif
        // process the next node and give the current node as the previous one
        head = reverse(next,cur);
#ifdef DEBUG
        --dbglvl;
#endif

        // set the link pointer to the previous node
        cur->next = prev;
        dbgprt("POST cur->next=%d\n",prt(cur->next));
    } while (0);

    dbgprt("EXIT head=%d\n",prt(head));

    return head;
}

// addnode -- add node to tail of list
Node *
addnode(Node *head,int data)
{
    Node *newnode = malloc(sizeof(*newnode));
    Node *cur;
    Node *prev;

    newnode->next = NULL;
    newnode->data = data;
#ifdef CHECK
    newnode->visited = 0;
#endif

    // find the tail of the list
    prev = NULL;
    for (cur = head;  cur != NULL;  cur = cur->next)
        prev = cur;

    // add new node to list
    if (prev != NULL)
        prev->next = newnode;
    else
        head = newnode;

    return head;
}

// list_print -- print list
void
list_print(Node *head,const char *reason)
{
    Node *cur;

    printf("%s:",reason);

    for (cur = head;  cur != NULL;  cur = cur->next) {
        printf(" %d",cur->data);
#ifdef CHECK
        if (cur->visited) {
            printf(" DUP\n");
            exit(1);
        }
        cur->visited = 1;
#endif
    }

    printf("\n");

#ifdef CHECK
    for (cur = head;  cur != NULL;  cur = cur->next)
        cur->visited = 0;
#endif
}

// list_destroy -- destroy the list
void
list_destroy(Node *cur)
{
    Node *next;

    for (;  cur != NULL;  cur = cur->next) {
        next = cur->next;
        free(cur);
    }
}

// dotest -- test reverse function
void
dotest(int max)
{
    Node *head = NULL;

#ifdef DEBUG
    dbglvl = 0;
#endif

    // create a list
    for (int idx = 1;  idx <= max;  ++idx)
        head = addnode(head,idx);

    // show the original list
    list_print(head,"Forward");

    // reverse the list
    head = reverse(head,NULL);

    // show the reversed list
    list_print(head,"Reverse");

    // destroy the test list
    list_destroy(head);
}

int
main(void)
{

    dotest(8);

    return 0;
}

Here's the program output:

Forward: 1 2 3 4 5 6 7 8
Reverse: 8 7 6 5 4 3 2 1

Here's the program output with the debug printf enabled:

Forward: 1 2 3 4 5 6 7 8
DBG/0: BEG cur=1 prev=-1 next=2
DBG/1: BEG cur=2 prev=1 next=3
DBG/2: BEG cur=3 prev=2 next=4
DBG/3: BEG cur=4 prev=3 next=5
DBG/4: BEG cur=5 prev=4 next=6
DBG/5: BEG cur=6 prev=5 next=7
DBG/6: BEG cur=7 prev=6 next=8
DBG/7: BEG cur=8 prev=7 next=-1
DBG/7: SETHEAD head=8 head->next=7
DBG/7: EXIT head=8
DBG/6: POST cur->next=6
DBG/6: EXIT head=8
DBG/5: POST cur->next=5
DBG/5: EXIT head=8
DBG/4: POST cur->next=4
DBG/4: EXIT head=8
DBG/3: POST cur->next=3
DBG/3: EXIT head=8
DBG/2: POST cur->next=2
DBG/2: EXIT head=8
DBG/1: POST cur->next=1
DBG/1: EXIT head=8
DBG/0: POST cur->next=-1
DBG/0: EXIT head=8
Reverse: 8 7 6 5 4 3 2 1