CODEWITHSUNDEEP
c++crecursiontail-call-optimization
croyd
croyd

Reputation: 1105

Print a linked list backwards in constant space and linear time using recursion

It seems to me like it should be possible to print a circular linked list backwards in constant space and linear time using recursion and tail-call-optimization. However, I am having difficulty due to trying to print the current element after making the recursive call. By inspecting the disassembly, I see that the function is being called and not jumped to. If I change it to print forwards instead of backwards, the function call is properly eliminated.

I have seen this related question, however I am specifically interested in solving it using recursion and TCO.

The code I am using:

#include <stdio.h>

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


void bar(struct node *elem, struct node *sentinel)
{
    if (elem->next == sentinel) {
        printf("%d\n", elem->data);
        return;
    }
    bar(elem->next, sentinel), printf("%d\n", elem->data);
}

int main(void)
{
    struct node e1, e2;
    e1.data = 1;
    e2.data = 2;
    e1.next = &e2;
    e2.next = &e1;
    bar(&e1, &e1);
    return 0;
}

and compiling with

    $ g++ -g -O3 -Wa,-alh test.cpp -o test.o

update: solved using Joni's answer with slight modifications for a circular list

void bar(struct node *curr, struct node *prev, struct node *sentinel,
    int pass)
{
    if (pass == 1) printf("%d\n", curr->data);
    if (pass > 1) return;
    if ((pass == 1) && (curr == sentinel))
        return;

    /* reverse current node */
    struct node *next = curr->next;
    curr->next = prev;

    if (next != sentinel) {
        /* tail call with current pass */
        bar(next, curr, sentinel, pass);
    } else if ((pass == 1) && (next == sentinel)) {
        /* make sure to print the last element */
        bar(next, curr, sentinel, pass);
    } else {
        /* end of list reached, go over list in reverse */
        bar(curr, prev, sentinel, pass+1);
    }
}

Upvotes: 1

Views: 783

Answers (2)

Karoly Horvath
Karoly Horvath

Reputation: 96286

Update: this answer is misleading (please downvote it!), it's only true if you cannot modify the data structure.

It's impossible. Recursion and constant space are contradictory requirements in this task.

I understand you would like to use TCO, but you can't as you have extra work to do after the recursive call.

From wikipedia http://en.wikipedia.org/wiki/Tail_call:

In computer science, a tail call is a subroutine call that happens inside another procedure as its final action.

Upvotes: 4

Joni
Joni

Reputation: 111349

To benefit from tail-call optimization you have to reorganize the code. Here's one way to do it:

void bar(struct node *curr, struct node *prev, int pass)
{
    if (pass == 1) printf("%d\n", curr->data);
    if (pass > 1) return;

    /* reverse current node */
    struct node *next = curr->next;
    curr->next = prev;

    if (next) {
        /* tail call with current pass */
        bar(next, curr, pass);
    } else {
        /* end of list reached, go over list in reverse */
        bar(curr, NULL, pass+1);
    }
}

This function assumes that the end of the list is signaled by NULL. The list is traversed in two passes: first to reverse it in-place, second to print the elements and reverse it again. And, as far as I can tell, gcc -O3 does a tail-call optimization so the algorithm runs in constant space.

To call this function use:

bar(&e1, NULL, 0);

Upvotes: 2

Related Questions