question about pointers and recursion 1

[rsshetty]

How would I construct a linked list using recursion.
void main()
{
Rec(5);
}

void Rec(int num)
{
if(num==5)
return;
else
<--what if I wanted to start building a linked list here with the current value of num
Rec(num+1);
}

I am not sure how to connect the current node to the next node because the next node is appended in a whole new recursive call.

rsshetty.

It's always in the details.

 

[Zyrenthian]

void Rec(int num)
{
if(!num)
return;

list.Add(num);
Rec(num-1);
}

Assuming list.Add will insert at the beginning, the implimentation above will be a queue. Placing the Add call AFTER Rec(num-1); will set it up as a stack

Matt

 

[rsshetty]

Could you elaborate on ListAdd. That's what's giving me trouble.

It's always in the details.

 

[Zyrenthian]

Usually it looks something like

struct node
{
int value;
node* pNext;
};

ListAdd(int x)
{
node* newNode = (node*)malloc(sizeof(node));
newNode->value = x;
newNode->pNext = head;
}

That is the basic gist... Also, been a while since I worked in C so check the syntax :-D

Matt

 

[rsshetty]

Oh the syntax is not a problem. What I am interested in is "head". How do you keep track of it?

It's always in the details.

 

[Zyrenthian]

One more thing...

after newNode->pNext = head;
you need a head = newNode;

Sorry bout that.

Matt

 

[rsshetty]

Hmm.. I'm still not clear on how you are keeping track of the list.

rsshetty.

It's always in the details.

 

[Salem]

Try this

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

struct list {
    struct list *next;
    int         n;
};

struct list *addlist ( struct list *head, int n ) {
    if ( head == NULL ) {
        head = malloc( sizeof *head );
        head->next = NULL;
        head->n = n;
    } else {
        head->next = addlist( head->next, n );
    }
    return head;
}
void printlist ( struct list *head ) {
    if ( head != NULL ) {
        printf( "%d\n", head->n );
        printlist( head->next );
    }
}
int main()
{
    struct list *head = NULL;   // empty list
    head = addlist( head, 1 );
    head = addlist( head, 2 );
    head = addlist( head, 3 );
    printlist( head );
}

--

 

[rsshetty]

Yes, now that's what I was asking for.
Thanks Salem.
(and thanks for trying Matt,I appreciate it!)

rsshetty.

It's always in the details.