+ Post New Thread
Results 1 to 8 of 8
Coding Thread, Any computer scientists out there? in Coding and Web Development; Hi all. I'm current struggling with a concept that I hope you could help with. I'm learning about recursion - ...
  1. #1


    Join Date
    Jan 2006
    Posts
    8,202
    Thank Post
    442
    Thanked 1,032 Times in 812 Posts
    Rep Power
    339

    Any computer scientists out there?

    Hi all.
    I'm current struggling with a concept that I hope you could help with.
    I'm learning about recursion - calling a function from within the same function. I can see that this produces cleaner code vs iteration inside a function but I'm struggling to see the advantage.

    Presumably recursion uses more memory than iteration as it has to work backwards through values in the stack. It certainly seems more complicated (to me at least) than iteration. So what is the advantage of this method? Is it faster? If so why?

  2. #2

    Join Date
    Mar 2013
    Location
    west sussex
    Posts
    519
    Thank Post
    74
    Thanked 26 Times in 26 Posts
    Rep Power
    15
    recursion is dangerous as well as you can exhaust the stack very quickly. you need to ensure that you have a conditional statement which ensures that it stops recursing when the condition is met otherwise not only will your program loop it will overflow the stack quickly.

    consider the following searching a folder for a specific file, it uses recursion to search sub folders and iteration to search the current folder (not sure it works 100% was bored waiting for centos to install)

    Code:
    entry find_file(string folder_name, string wanted) 
    {
        entry = get_first_entry(folder_name);
        while (entry != null) 
        {
            if (entry is folder)
            {
                entry2 = find_file(folder_name + "\\" + entry.name);
                if (entry2 != null)
                    return entry2;
            }
            else if (entry is file)
           {
                if (entry.name == wanted)
           }
           entry = get_next_entry(folder_name, entry);
        }
        return null;
    }

  3. #3

    Join Date
    Sep 2008
    Location
    England
    Posts
    271
    Thank Post
    6
    Thanked 70 Times in 62 Posts
    Rep Power
    53
    It depends on your data structure and your algorithm. The performance differences on a simple array will be minimal. Then you would want to use whatever makes the code most obvious to the reader, at least in the initial version. Once you have it working, you would use a debugger to find the slow bits and just improve them.

    When you start using linked lists and tree structures then recursion makes more sense. There are some other mathematical functions where it is also useful such as working out the factorial of a number.

    In a linked list, or tree, each object points to the next one or more objects. This next bit is from wikipedia:

    Code:
    struct node
    {
      int data;           // some integer data
      struct node *next;  // pointer to another struct node
    };
    Because the struct node data structure is defined recursively, procedures that operate on it can be implemented naturally as recursive procedures. The list_print procedure defined below walks down the list until the list is empty (i.e., the list pointer has a value of NULL). For each node it prints the data element (an integer). In the C implementation, the list remains unchanged by the list_print procedure.

    Code:
    void list_print(struct node *list)
    {
        if (list != NULL)               // base case
        {
           printf ("%d ", list->data);  // print integer data followed by a space
           list_print (list->next);     // recursive call on the next node
        }
    }
    Performing the above on a linked list with iteration would be slow, and you would probably have some similar code hidden somewhere anyway. Worst case, you might end up recursively going through the list each time you try and print an object. That would be relatively inefficient, see the next code block and imagine calling that in a 'for each' statement for each element in the list/array. Its important to understand the data structures your working on.

    Code:
    int list_index(struct node *list, int i)
    {
        if (list != NULL)               // base case
        {
           if (i == 0) {
             return (list->data); 
           }
           return list_index(list->next, i - 1);     // recursive call on the next node
        }
    }
    
    int list_length(struct node *list, int i = 0)
    {
        if (list != NULL)               // base case
        {
           return list_length(list->next, i + 1);     // recursive call on the next node
        } else {
           return i;
        }
    }
    
    for (int c = list_length(list, 0); 0; c ++) {
       printf("%d ", list_index(list, c));
    }
    Last edited by Chris_Cook; 5th May 2013 at 04:18 PM. Reason: fixed some errors in the code.

  4. Thanks to Chris_Cook from:

    CyberNerd (5th May 2013)

  5. #4


    Join Date
    Jan 2006
    Posts
    8,202
    Thank Post
    442
    Thanked 1,032 Times in 812 Posts
    Rep Power
    339
    Awesome answers. Thanks.

  6. #5
    Sam_Brown's Avatar
    Join Date
    Sep 2009
    Location
    Northampton
    Posts
    569
    Thank Post
    95
    Thanked 38 Times in 36 Posts
    Rep Power
    18

  7. #6

    jinnantonnixx's Avatar
    Join Date
    Mar 2011
    Location
    In the Calamatorium.
    Posts
    1,976
    Thank Post
    113
    Thanked 495 Times in 337 Posts
    Blog Entries
    2
    Rep Power
    284
    Recursion is useful for deleting sub-objects (folders, keys, etc) within a branch.

    In this post, I wrote a bit of code that uses recursion to delete a key branch. If the branch has sub-keys, it calls itself for each sub-key and so on.

    Windows 7 user profile failed error...... again!

    Code:
    Sub DeleteKey (thisKey)
    	'delete all subkeys
    	objReg.EnumKey HKEY_LOCAL_MACHINE, thisKey, arrSubKeys
    	If IsArray (arrSubKeys) Then
    		For Each strSubKey In arrSubKeys
    			'recursively delete the key
    			DeleteKey (thisKey & "\" & strSubKey)
    		Next
    	End If
    	
    	'delete the registry key
    	objReg.DeleteKey  HKEY_LOCAL_MACHINE,thisKey
    End sub

  8. #7

    dhicks's Avatar
    Join Date
    Aug 2005
    Location
    Knightsbridge
    Posts
    5,625
    Thank Post
    1,240
    Thanked 778 Times in 675 Posts
    Rep Power
    235
    Quote Originally Posted by CyberNerd View Post
    Presumably recursion uses more memory than iteration as it has to work backwards through values in the stack.
    In practice, modern compilers / interpreters have facilities to improve the speed / memory footprint of recursive functions - tail recursion and so on.

    So what is the advantage of this method? Is it faster? If so why?
    A single function call can be assigned to a parallel process, which can then be ran on a separate core / processor / whatever, so recursive functions tend to make for more easily parellel-isble functions. Probably not noticeable at the learning stage, but good when you get to the Big Data end of things and want your processing spread over as many compute nodes as are available.

  9. Thanks to dhicks from:

    CyberNerd (6th May 2013)

  10. #8
    box_l's Avatar
    Join Date
    May 2007
    Location
    Herefordshire
    Posts
    429
    Thank Post
    68
    Thanked 90 Times in 75 Posts
    Rep Power
    61
    @ sam_brown.

    I see what you did there..

SHARE:
+ Post New Thread

Similar Threads

  1. Any amateur astonomers out there?
    By Dos_Box in forum General Chat
    Replies: 9
    Last Post: 6th September 2010, 11:56 AM
  2. Any Wyse Experts out there?
    By tmcd35 in forum Thin Client and Virtual Machines
    Replies: 1
    Last Post: 13th May 2010, 12:10 PM
  3. Any XBMC users out there?
    By CHR1S in forum General Chat
    Replies: 12
    Last Post: 2nd November 2009, 11:37 AM
  4. Are there any Sharepoint Gurus out there?
    By Ben_Stanton in forum Virtual Learning Platforms
    Replies: 11
    Last Post: 24th January 2009, 10:51 AM

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

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