C - Using Recursion to Print Linked List

Question

I am required to write a function in C, that given a pointer to a linked list, will print out the elements in Python syntax: e.g. For the list consisting of 1,2,3,4 and 5, the function will print out [1, 2, 3, 4, 5].

I have tried to write the code as follows:

struct node {
    struct node *next;
    int       data;
};

void print_list(struct node *list) {
    printf("[");
    if (list == NULL) {
        printf("]");
    } else {
        printf("%d", list->data);
        if (list->next != NULL) {
            printf(", ");
        }
        print_list(list->next);
    }
}

Output looks like this: [1, [2, [3, [4, [5[]

I understand that every time the function calls itself, "[" will be printed. is there a way to print "[" only when the function is called for the first time?

How about printing it _before_ calling the recursive function? — Ctx, Jul 18 '17 at 12:33
Yes. Second option, add a flag to the parmeters that tells you if you should print a bracket — CIsForCookies, Jul 18 '17 at 12:34
I would but I"m not really sure if I'm allowed to do it as this is for homework and I think the whole thing is meant to be printed within the function — M.Ng, Jul 18 '17 at 12:34
I don't think I'm allowed to change the parameters. I'm starting to wonder if this problem is even possible to solve — M.Ng, Jul 18 '17 at 12:37
If recursion wasn't an actual *part of the requirement* (it might be if this is a practice assignment), don't do things like this recursive — , Jul 18 '17 at 12:54

score 5 · Accepted Answer · edited Jul 18 '17 at 14:48

5

You could create a wrapper function for printing braces. In between prints, call the actual recursive function, like this:

void print_list(struct node *list) {
    putchar('[');
    print_list_helper(list);
    putchar(']');

void print_list_helper(struct node *list) {
    if (list != NULL)
        printf("%d", list->data);
        if (list->next != NULL) {
            printf(", ");
        }
        print_list_helper(list->next);
    }
}

Edit: As pointed out by Felix Palmen, a static variable is an option, but not the best. It works only when you call the function the first time. After that, the counter has to be reset, which isn't easy to do and makes the recursive function impure.

An example of the use of static:

#include <stdio.h>

void foo() {
    static int x = 0;
    printf("x In foo: %d\n", x);
    x++;
}

int main() {
    int i;
    for(i = 0; i < 5; i++) {
        foo();
    }

    return 0;
}

This prints:

 $ ./a.out 
x In foo: 0
x In foo: 1
x In foo: 2
x In foo: 3
x In foo: 4

A static integer retains its value in between function calls. So, you'd be able to use it the very first time you call your recursive function, but you'd need to reset it every time you hit the base case.

Another example of static:

void foo() {
    static int x = 0; // initialization (done ONCE!)
    printf("x In foo: %d\n", x);
    x++;
    if(x%2 == 0) x = 0; // reassignment (done as many times as you like)
}
... // everything else is the same

This gives:

$ ./a.out   
x In foo: 0
x In foo: 1
x In foo: 0
x In foo: 1
x In foo: 0

edited Jul 18 '17 at 14:48

chux - Reinstate Monica

143,097
13
135
256

answered Jul 18 '17 at 12:35

cs95

379,657
97
704
746

Is it possible to solve the problem without creating a wrapper function or global variables? – M.Ng Jul 18 '17 at 12:43
Good idea, but the name `_print_list` is a poor one (since identifiers starting with an underscore are implementation reserved). Should be `print_list_content` – Basile Starynkevitch Jul 18 '17 at 12:43
@M.Ng It is, with a static integer variable. I don't want to sound redundant, since [this](https://stackoverflow.com/a/45167070/4909087) answer already proposed it. – cs95 Jul 18 '17 at 12:44
@BasileStarynkevitch Thanks. I come from the world of python where private objects are prepended with an underscore :) – cs95 Jul 18 '17 at 12:45
What's a static variable? and how would it help with the situation – M.Ng Jul 18 '17 at 12:48
@M.Ng Added an example to help you understand. Even across recursive calls, it retains its value. – cs95 Jul 18 '17 at 12:52
I'm not really following the example, after void foo() executes, x is incremented to 1. But when the function is called again, won't x be reseted back to zero? – M.Ng Jul 18 '17 at 13:00
@cᴏʟᴅsᴘᴇᴇᴅ see my comment on the other answer. Additionally, the function would only work a single time as expected this way. Your original idea is the only one feasible if it really **has** to be done recursive and you're not allowed to change the function signature. – Jul 18 '17 at 13:01
@FelixPalmen Oh.. great point. Did _not_ consider that. Thanks for pointing it out. I've rolled back my answer. – cs95 Jul 18 '17 at 13:03
@M.Ng On second thoughts, a static variable is not a good idea, because you need to reset it afterwards which is not possible. – cs95 Jul 18 '17 at 13:03
@M.Ng Just to clarify, the _best_, most cleanest way to do this is using a wrapper. There's just no better alternative that doesn't involve jumping through hoops and creating spaghetti code. – cs95 Jul 18 '17 at 13:06
1

@cᴏʟᴅsᴘᴇᴇᴅ it is *possible* to reset it e.g. in the tail of the recursive call. Still, it defeats the typical purpose of recursion, so I think your original answer is indeed the best one. – Jul 18 '17 at 13:06
I still don't understand the difference between a static and normal variable. Might try again tomorrow when I'm not so sleep deprived – M.Ng Jul 18 '17 at 13:06
@cᴏʟᴅsᴘᴇᴇᴅ yeah the wrapper one makes the most sense to me – M.Ng Jul 18 '17 at 13:08
@M.Ng After what Felix said, I will not advocate them for your use. However, if you wish to learn more, you can look here: https://stackoverflow.com/questions/572547/what-does-static-mean – cs95 Jul 18 '17 at 13:08
@M.Ng inside a scope other than the file scope (so, e.g. inside a function), the default *storage duration* of a variable is *automatic*, this means it lives exactly as long as it is *in scope* during execution. Therefore: call the function again, get a **new** variable. You **can** give it *static storage duration* with the `static` keyword, this means its lifetime is for the whole execution time of your program (get **the same** variable with each call). – Jul 18 '17 at 13:08
But even if the variable is the same one for multiple function calls, it just gets reset to zero which I dont get :/ ugh i lost the picture so I can't describe what i'm confused over – M.Ng Jul 18 '17 at 13:11
2

@M.Ng no, in something like `static int print_start = 0;`, the `= 0` isn't an assignment but an *initialization*. Initialization only ever happens once per lifetime of the variable, regardless of where it is declared. Assignment would look like `static int print_start; print_start = 0;` and this would indeed assign in each and every call. – Jul 18 '17 at 13:14
Err, @M.Ng I added a second example. Hopefully this will clear it. – cs95 Jul 18 '17 at 13:16
@M.Ng Fantastic, glad we could help :) – cs95 Jul 18 '17 at 13:22

Billy Ferguson · Answer 2 · 2017-07-18T15:25:18.870

1

You could do it with a static integer.

struct node {
    struct node *next;
    int       data;
};

void print_list(struct node *list) {
    static int print_start = 0;
    if (print_start == 0) {
        printf("[");
    }
    if (list == NULL) {
        printf("]");
        print_start = 0;
    } else {
        print_start++;
        printf("%d", list->data);
        if (list->next != NULL) {
            printf(", ");
        }
        print_list(list->next);
    }
}

edited Jul 18 '17 at 15:25

answered Jul 18 '17 at 12:39

Billy Ferguson

1,429
11
23

3

you have to also set print_start =0 while printing closing bracket – Shubham Agrawal Jul 18 '17 at 12:40
Good solution. +1 – cs95 Jul 18 '17 at 12:53
1

If this is for practicing recursion, I don't think it's a good solution. Recursive functions typically aim to be *pure* functions, a global variable defeats that purpose. If on the other hand recursion isn't required, there are much better iterative approaches. – Jul 18 '17 at 12:57
The if inside the outer else was theoritically useless. – Karim Manaouil Jul 18 '17 at 14:11
I tried to give a solution with the least amount of modifications to the original solution. However, the solution that is pure is the only solution. This solution will work, however like @FelixPalmen it needs to be pure. I made it reset the counter to zero when it hits the end of the linked list so it works for OP's needs now. – Billy Ferguson Jul 18 '17 at 15:21

score 0 · Answer 3 · answered Jul 18 '17 at 12:35

use global variable and change your code to

int count=0;
void print_list(struct node *list) {
    if(count==0)
        printf("[");
    if (list == NULL) {
        printf("]");
    } else {
        printf("%d", list->data);
        if (list->next != NULL) {
            printf(", ");
        }
        print_list(list->next);
    }
count++;

}

score 0 · Answer 4 · answered Jul 18 '17 at 13:55

0

Add an additional parameter which shows if it was called from outside or recursively. Most elegant way but will cost you some stack.

answered Jul 18 '17 at 13:55

0___________

60,014
4
34
74

C - Using Recursion to Print Linked List

4 Answers4