Please help me understand this question.
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7

Thread: Please help me understand this question.

  1. #1
    Join Date
    Jul 2005
    Posts
    910

    Please help me understand this question.

    A question. How to read a singly linked list backwards? Here is the implementation,
    Code:
    void ReadListBackward(node* head)
    {
    	node* p = head;
    	
    	if(!p)
    		return;
    
    	if(p->next)
    		ReadListBackward(p->next);
    	else
    	{
    		printf("%d\n", p->data);
    		return;
    	}
    
    	printf("%d\n", head->data);
    }
    Could any guru here help me understand why it works? Thanks a lot.

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Please help me understand this question.

    Quote Originally Posted by LarryChen View Post
    Could any guru here help me understand why it works?
    It works because of recursion (a function calls itself repeatedly until a termination criterion is met).

    Here the ReadListBackward function is calling itself and each time advancing along the list in the forward direction. Finally when the end is reached all accumulated ReadListBackward calls are terminated in reverse order one by one. It's during this "rewinding" process the printing takes place so it will be in reverse. If you put the print immediately before the ReadListBackward call the order would be in the forward direction instead.

    A warning. If the list is very long the number of accumulated ReadListBackward calls may be too many which will result in a stack overflow.

    And the ReadListBackward function is little too complicated. It's possible to do this with just one print statement.
    Last edited by nuzzle; June 2nd, 2013 at 12:42 AM.

  3. #3
    Join Date
    Jul 2005
    Posts
    910

    Re: Please help me understand this question.

    Quote Originally Posted by nuzzle View Post
    It works because of recursion (a function calls itself repeatedly until a termination criterion is met).

    Here the ReadListBackward function is calling itself and each time advancing along the list in the forward direction. Finally when the end is reached all accumulated ReadListBackward calls are terminated in reverse order one by one. It's during this "rewinding" process the printing takes place so it will be in reverse. If you put the print immediately before the ReadListBackward call the order would be in the forward direction instead.

    A warning. If the list is very long the number of accumulated ReadListBackward calls may be too many which will result in a stack overflow.

    And the ReadListBackward function is little too complicated. It's possible to do this with just one print statement.
    Thanks for your reply. First of all, let me take an example here,
    assume there is four nodes in the list, node 1, node 2, node 3, node 4 like this,

    1=>2=>3=>4

    So the calling sequence would be like this,

    ReadListBackward(1)=>ReadListBackward(2)=>ReadListBackward(3)=>ReadListBackward(4)=>print(4)=>return

    So when ReadListBackward(4) returns, the control goes to ReadListBackward(3). Here what I really don't understand is that since node 3's next node is always not NULL, so how come it will print out 3? Thanks a lot.

  4. #4
    Join Date
    Sep 2001
    Location
    Québec, Canada
    Posts
    1,923

    Re: Please help me understand this question.

    It will work because after returning, the line "printf("%d\n", head->data);" will be executed, which will print 3.

    JeffB
    CodeGuru VB FAQ Visual Basic Frequently Asked Questions
    VB Code color Tool to color your VB code on CodeGuru
    Before you post Importants informations to know before posting

  5. #5
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,441

    Re: Please help me understand this question.

    So when ReadListBackward(4) returns, the control goes to ReadListBackward(3).
    Correct. The program resumes at

    Code:
    printf("%d\n", head->data);
    as this is ReadListBackward(3) then head->data is 3 and hence 3 is printed. When a function calls itself it re-enters the function and creates a new set of non-static variables. When the function exits, it goes back to the place in the function from which it was called with the same variable values that existed in the function before the call. This is called function recursion.

    You might find this useful
    http://www.dcs.bbk.ac.uk/~roger/cpp/week15.htm
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  6. #6
    Join Date
    Jul 2005
    Posts
    910

    Re: Please help me understand this question.

    Quote Originally Posted by 2kaud View Post
    Correct. The program resumes at

    Code:
    printf("%d\n", head->data);
    as this is ReadListBackward(3) then head->data is 3 and hence 3 is printed. When a function calls itself it re-enters the function and creates a new set of non-static variables. When the function exits, it goes back to the place in the function from which it was called with the same variable values that existed in the function before the call. This is called function recursion.

    You might find this useful
    http://www.dcs.bbk.ac.uk/~roger/cpp/week15.htm
    I got it. Thank you very much!

  7. #7
    Join Date
    May 2009
    Posts
    2,413

    Re: Please help me understand this question.

    Quote Originally Posted by LarryChen View Post
    I got it.
    As I indicated, the recursive function can be simplified and then it becomes even clearer how it works,
    Code:
    void ReadListBackward(node* p) {
       if (!p) {
    	printf("T!\n"); // recursion terminates
       } else {
    	printf("F: %d\n", p->data); // print in forward direction
    	ReadListBackward(p->next); // recursive call
    	printf("B: %d\n", p->data); // print in backward direction
       }
    }
    Last edited by nuzzle; June 4th, 2013 at 01:04 AM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center