Make Recursive function 'Tail-Recursive'

This is a discussion on Make Recursive function 'Tail-Recursive' within the C Programming forums, part of the General Programming Boards category; Hi, so basically I made a singly-linked list and to navigate through it I have two methods that I've proposed, ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    5

    Make Recursive function 'Tail-Recursive'

    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

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,235
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  4. #4
    Registered User
    Join Date
    Oct 2008
    Posts
    19
    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.

  5. #5
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    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.

  6. #6
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    602
    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.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    Quote Originally Posted by dp2452 View Post
    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!
    Last edited by iMalc; 12-03-2009 at 11:52 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by iMalc View Post
    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.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Seg Fault in Compare Function
    By tytelizgal in forum C Programming
    Replies: 1
    Last Post: 10-25-2008, 03:06 PM
  2. Need help designing a recursive function.
    By broli86 in forum C Programming
    Replies: 3
    Last Post: 07-24-2008, 12:45 PM
  3. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  4. Calling a Thread with a Function Pointer.
    By ScrollMaster in forum Windows Programming
    Replies: 6
    Last Post: 06-10-2006, 08:56 AM
  5. Interface Question
    By smog890 in forum C Programming
    Replies: 11
    Last Post: 06-03-2002, 05:06 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21