Make Recursive function 'Tail-Recursive'

**dp2452** · 12-03-2009

Hi, so basically I made a singly-linked list and to navigate through it I have two methods that I've proposed, either iteratively or recursively. Both work but apparently my recursive function is not tail-recursive so it is eating up all my stack memory. Ideally I want to make use of the recursive search function rather than the iteration. So here's what I have:

Recursive Search

Code:

node rec_search (node n, int i)
{
	if (i == 0)
	{
		return n;
	}
	else
	{
		return rec_search (n->next, i-1);
	}
}

Iterative Search

Code:

node rec_search (node n, int i)
{
	while (i > 0)
	{
		n = n->next;
		i--;
	}
	return n;
}

I thought that my recursive function was tail-recursive to use constant space but apparently it's not. So if anyone could help me re-write this to not use anymore stack memory as I need that would much appreciated!

Thank you

**MK27** · 12-03-2009

I do not think tail recursion is common or advantageous in C.

The best way to do this is the iterative method, anyway. It will be faster and use less stack space.

**brewbuck** · 12-03-2009

Recursive processing with unbounded depth in a language that doesn't support native tail-recursion is silly. Everybody in the universe processes linked lists iteratively.

**glennik** · 12-03-2009

From my point of view, which can be cluttered by the fact that the the type node is not presented, is that you are handling the pointers wrong, which will result it random i values. The obvoius result of this behaviour is that the program runs until the pc run out of stack memory.

**itCbitC** · 12-03-2009

IMHO the list traversal technique doesn't make sense.
For a singly linked list, each node is linked to the next one starting at the head of the list.
Starting at the tail of the list, won't n->next be a NULL pointer?
Post the typedef of node.

**slingerland3g** · 12-03-2009

What is the value of i during your first call to rec_search(). Try setting your conditional to '(if i >= 0)'.

My first though is that your conditional is never satisfied.

**iMalc** · 12-04-2009

Originally Posted by dp2452

I thought that my recursive function was tail-recursive to use constant space but apparently it's not. So if anyone could help me re-write this to not use anymore stack memory as I need that would much appreciated!

It is tail-recursive. That doesn't mean it will use constant space though. The compiler is free to use such an optimisation or not, at its discretion.
You can either write it tail-recursively and cross your fingers, or you can write it iteratively and rest comfortably in the knowledge that it will always use constant space no matter what compiler, or compiler version, or compilation options, phase of the moon etc...

In this case though I think that either implementation is an abomination. Accessing the Nth node of a list which may or may not even have N nodes, is both a performance crime and an accident waiting to happen!

**quzah** · 12-04-2009

Originally Posted by iMalc

In this case though I think that either implementation is an abomination. Accessing the Nth node of a list which may or may not even have N nodes, is both a performance crime and an accident waiting to happen!

Use a circular list.

Quzah.

Thread: Make Recursive function 'Tail-Recursive'

Thread Tools

Search Thread

Display

Make Recursive function 'Tail-Recursive'

Similar Threads

Seg Fault in Compare Function

Need help designing a recursive function.

How to fix misaligned assignment statements in the source code?

Calling a Thread with a Function Pointer.

Interface Question